codeforce Pashmak and Buses(dfs枚举)

/*
   题意：n个同学，k个车， 取旅游d天！
   要求所有的学生没有两个或者两个以上的在同一辆车上共同带d天！ 输出可行的方案！

   对于d行n列的矩阵，第i行第j列表示的是第i天第j个同学所在的车号！
   也就是保证所有行不全相同，即每一列都是不相同的！
   如果每一列都不相同就是表示第j个同学（第j列）在这d天中不会和其他同学（列）在这d天中 都在同一辆车中！ 

   思路：对于每一列我们枚举d天该学生所在的车号！它的下一列只保证有一个元素和它不同就行了！依次下去！

   还有一共有 d 个位置来填充车号（1....k）！每一个位置的数字都可以是（1...k）中的一个数字。
   总共的枚举次数为 k^d， 一共有n个同学，枚举n次就可以了，所以有 k^d >=n才有解！
*/
#include<iostream>
#include<cstdio>
using namespace std;

int ret[1005][1005];
int a[1005];
int n, k, d;
int cnt;
bool dfs(int cur){
   if(cur>d){
        ++cnt;
        for(int i=1; i<=d; ++i)
       ret[i][cnt]=a[i];
        if(cnt==n)
          return true;
     return false;
   }
   for(int i=1; i<=k; ++i){
       a[cur]=i;
       if(dfs(cur+1))//强力剪枝....搜索完成后不在进行搜索！
          return true;
   }
   return false;
}

int main(){
   while(scanf("%d%d%d", &n, &k, &d)!=EOF){
          cnt=0;
          int kk=k;
          bool flag=false;
          for(int i=1; i<=d; ++i){//保证k^d>=n才可能有解！
                if(kk>=n){
              flag=true;
              break;
          }
          kk*=k;
       }
       if(flag){
           dfs(1);
           for(int i=1; i<=d; ++i){
              for(int j=1; j<=n; ++j){
                 printf("%d", ret[i][j]);
                 if(j!=n)  printf(" ");
              }
              printf("\n");
           }
       }
       else printf("-1\n");
   }
   return 0;
}