1 /* 2 題意：n個同學，k個車， 取旅游d天！ 3 要求所有的學生沒有兩個或者兩個以上的在同一輛車上共同帶d天！ 輸出可行的方案！ 4 5 對于d行n列的矩陣，第i行第j列表示的是第i天第j個同學所在的車號！ 6 也就是保證所有行不全相同，即每一列都是不相同的！ 7 如果每一列都不相同就是表示第j個同學（第j列）在這d天中不會和其他同學（列）在這d天中 都在同一輛車中！ 8 9 思路：對于每一列我們枚舉d天該學生所在的車號！它的下一列只保證有一個元素和它不同就行了！依次下去！ 10 11 還有一共有 d 個位置來填充車號（1....k）！每一個位置的數字都可以是（1...k）中的一個數字。 12 總共的枚舉次數為 k^d， 一共有n個同學，枚舉n次就可以了，所以有 k^d >=n才有解！ 13 */ 14 #include<iostream> 15 #include<cstdio> 16 using namespace std; 17 18 int ret[1005][1005]; 19 int a[1005]; 20 int n, k, d; 21 int cnt; 22 bool dfs(int cur){ 23 if(cur>d){ 24 ++cnt; 25 for(int i=1; i<=d; ++i) 26 ret[i][cnt]=a[i]; 27 if(cnt==n) 28 return true; 29 return false; 30 } 31 for(int i=1; i<=k; ++i){ 32 a[cur]=i; 33 if(dfs(cur+1))//強力剪枝....搜索完成后不在進行搜索！ 34 return true; 35 } 36 return false; 37 } 38 39 int main(){ 40 while(scanf("%d%d%d", &n, &k, &d)!=EOF){ 41 cnt=0; 42 int kk=k; 43 bool flag=false; 44 for(int i=1; i<=d; ++i){//保證k^d>=n才可能有解！ 45 if(kk>=n){ 46 flag=true; 47 break; 48 } 49 kk*=k; 50 } 51 if(flag){ 52 dfs(1); 53 for(int i=1; i<=d; ++i){ 54 for(int j=1; j<=n; ++j){ 55 printf("%d", ret[i][j]); 56 if(j!=n) printf(" "); 57 } 58 printf("\n"); 59 } 60 } 61 else printf("-1\n"); 62 } 63 return 0; 64 }
?
)
)
)
)
