从零开始算法之路 ----托米航空公司

太过爱你忘了你带给我的痛 2022-04-24 09:26 168阅读 0赞

链接：[https://ac.nowcoder.com/acm/problem/16407][https_ac.nowcoder.com_acm_problem_16407]  
来源：牛客网

**题目描述**

> 托米老师靠才华与颜值发家致富后，开了一家航空公司，公司的口号是“您想飞，我们便做您的翅膀~让您每次飞行都有独特的体验！”

但是现在有一个小小的问题需要解决，托米家的飞机每排有M个座位，有N排座位。因此座椅形成了M × N的网格（忽略过道）,公司为每次航班都出售K张票。  
为了满足口号中的“翅膀”部分，座位必须遵守以下规则：座位被占用时，座位正前方和座位后方的座位以及当前座位左边和右边必须是空的(大概是因为这个飞机会很大吧，boss就是这么任性哼)。  
然后为了满足口号中的“独特体验”部分。公司则是对每一趟航班飞机的座位采取不同的安排，如果这一趟的某个座位是占用的，而另一趟的座位是空的，则这两趟飞机座位安排是不同的。  
给你三个数字M，N和K。  
现在需要从这些座位中选出k个合法的座位。由于这个数字可能非常大，我们只求它对420047取模的结果。

**输入描述:**

输入的第一行包含一个整数T，表示指定测试用例的数量。  
每个测试用例前面都有一个空白行。  
每个测试用例由包含三个整数M，N和K的一行组成。

**输出描述:**

对于每个测试用例输出一行，表示答案对420047取模的结果。

示例1

**输入**

3
    
    2 3 2
    
    2 4 4
    
    2 5 1

**输出**

8
    2
    10

**备注:**

T≤10
    
    N*M<=80, K<=4

思路：定义一个二维数组，一个个遍历过去，如果符合题目条件（座位必须遵守以下规则：座位被占用时，座位正前方和座位后方的座位以及当前座位左边和右边必须是空的），选出该座位并标记，详细看代码。

**代码：**

#include<stdio.h>
    #include<string.h>
    int M, N, K, T;
    int a[80][80];
    //  h = K
    long long  select_seat(int h, int istart, int jstart){	
    	long long sum = 0;
    	//如果 k 个座位都选好了，返回选座位的 案数 sum
    	//返回 1 表示一种选坐方案数 
    	if( h == 0)
    	    return 1;
    	
    	for(int i = istart; i < N; i++){
    		
    	    for(int j = jstart; j < M; j++){	    	    
    	    	// a[i-1][j]前面的座位  a[i][j-1]左边的座位  ==0 表示没有人坐 
    	    	//判断每一个位置是否左边和前面是否有人，如果没人该座位可选 
    	    	if( i-1 >= 0 && j-1 >= 0 && a[i-1][j] ==0 && a[i][j-1] ==0){
    			        //标记为 h 表示有人坐，该位置已被选 
    	    	    	a[i][j] = h;
    	    	    	//选好一个位置，递归调用选下一个，知道 h == 0 ，即 k 个座位已经选好，return 1 
    	    	       sum += select_seat( h-1, i ,j+1);
    	    	}
    			else if(i-1 <0 && j -1 <0 ){
    				    //标记为 h 表示有人坐，该位置已被选  
    	    	    	a[i][j] = h;
    	    	    	//选好一个位置，递归调用选下一个，知道 h == 0 ，即 k 个座位已经选好，return 1 
    	    	       sum += select_seat( h-1, i ,j+1);
    			} 
    			else if(i-1 < 0 && j -1 >= 0 &&  a[i][j-1] ==0){
    					 //标记为 h 表示有人坐，该位置已被选 
    	    	    	a[i][j] = h;
    	    	    	//选好一个位置，递归调用选下一个，知道 h == 0 ，即 k 个座位已经选好，return 1
    	    	        sum += select_seat( h-1, i ,j+1);
    			}
    			else if(j-1 < 0 && i-1 >=0 &&a[i-1][j] ==0){
    			    	//标记为 h 表示有人坐 
    	    	       a[i][j] = h;
    	    	       //选好一个位置，递归调用选下一个，知道 h == 0 ，即 k 个座位已经选好，return 1
    	    	       sum += select_seat( h-1, i ,j+1);
    			}
    			//选过的每一个位置，选过之后都归 0 
    			a[i][j] =0;
    		}
    		// 第一轮循环玩了之后，第一个位置一定从每一排的第一个位置开始 
    		jstart = 0;  
    		
    	}
    	  
    	return sum;	
    }
    
    
    int main(){
    	memset(a, 0, sizeof(a));
    	int count = 0;   
        scanf("%d", &T);
    	while(T){		
    		scanf("%d %d %d", &M, &N, &K);
    		//
    		count = select_seat( K, 0, 0)%420047;
    		printf("%d\n",count);		
    		T--;
    	}
    	return 0;
    }

[https_ac.nowcoder.com_acm_problem_16407]: https://ac.nowcoder.com/acm/problem/16407