UVa 11846 – Finding Seats Again

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2946

题意：

有一个 n*n（n<20）的座位矩阵里坐着k（k≤26）个研究小组。
每个小组的座位都是矩形形状。输入每个小组组长的位置和该组的成员个数，找到一种可能的座位方案。

分析：

深搜 + 剪枝，以矩形为搜索对象，每一层选择一个尚未放置字母的位置，作为矩形的左上角，向行和列依次扩展。

如果选择的矩形中只有一个小组，且其面积等于小组的成员个数，则在这个矩形内放置字母，然后递归下一层。

矩形的面积应不超过 9，在向列扩展的过程中可以对列的范围进行剪枝，具体见代码。

代码：

 #include <cstdio>
 #include <cstring> int n, k;
 char seat[][], ans[][]; bool dfs(int id, char ch){
     while(ans[id/n][id%n] != '.') id++;
     if(id == n * n) return true;
     int sr = id / n, sc = id % n, ec = n;
     for(int r = sr; r < n; r++){
         for(int c = sc; c < ec; c++){
             if(ans[r][c] != '.') { ec = c;  break; }
             int sum = (r - sr + ) * (c - sc + );
             if(sum > ) { ec = c;  break; }
             int digit = ;
             bool valid = true;
             for(int t = sr; t <= r; t++){
                 for(int i = sc; i <= c; i++){
                     if(seat[t][i] != '.'){
                         if(digit != ){ valid = false;  break; }
                         digit = seat[t][i] - '';
                     }
                 }
                 if(!valid) break;
             }
             if(!valid) { ec = c;  break; }
             if(digit < sum) { ec = c;  break; }
             if(digit > sum) continue;
             for(int t = sr; t <= r; t++){
                 for(int i = sc; i <= c; i++) ans[t][i] = ch;
             }
             if(dfs(id + c - sc + , ch + )) return true;
             for(int t = sr; t <= r; t++){
                 for(int i = sc; i <= c; i++) ans[t][i] = '.';
             }
         }
     }
     return false;
 } int main(){
     while(scanf("%d%d", &n, &k) && n){
         memset(ans, '.', sizeof(ans));
         for(int r = ; r < n; r++) scanf("%s", seat[r]);
         dfs(, 'A');
         for(int r = ; r < n; r++){
             for(int c = ; c < n; c++) printf("%c", ans[r][c]);
             printf("\n");
         }
     }
     return ;
 }

总结：

搜索对象的选取很重要，若选取不当，则会运行超时。