链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2946
题意：
有一个 n*n（n<20）的座位矩阵里坐着k（k≤26）个研究小组。
每个小组的座位都是矩形形状。输入每个小组组长的位置和该组的成员个数，找到一种可能的座位方案。
分析：
深搜 + 剪枝，以矩形为搜索对象，每一层选择一个尚未放置字母的位置，作为矩形的左上角，向行和列依次扩展。
如果选择的矩形中只有一个小组，且其面积等于小组的成员个数，则在这个矩形内放置字母，然后递归下一层。
矩形的面积应不超过 9，在向列扩展的过程中可以对列的范围进行剪枝，具体见代码。
代码：
1 #include <cstdio> 2 #include <cstring> 3 4 int n, k; 5 char seat[25][25], ans[25][25]; 6 7 bool dfs(int id, char ch){ 8 while(ans[id/n][id%n] != '.') id++; 9 if(id == n * n) return true; 10 int sr = id / n, sc = id % n, ec = n; 11 for(int r = sr; r < n; r++){ 12 for(int c = sc; c < ec; c++){ 13 if(ans[r][c] != '.') { ec = c; break; } 14 int sum = (r - sr + 1) * (c - sc + 1); 15 if(sum > 9) { ec = c; break; } 16 int digit = 99; 17 bool valid = true; 18 for(int t = sr; t <= r; t++){ 19 for(int i = sc; i <= c; i++){ 20 if(seat[t][i] != '.'){ 21 if(digit != 99){ valid = false; break; } 22 digit = seat[t][i] - '0'; 23 } 24 } 25 if(!valid) break; 26 } 27 if(!valid) { ec = c; break; } 28 if(digit < sum) { ec = c; break; } 29 if(digit > sum) continue; 30 for(int t = sr; t <= r; t++){ 31 for(int i = sc; i <= c; i++) ans[t][i] = ch; 32 } 33 if(dfs(id + c - sc + 1, ch + 1)) return true; 34 for(int t = sr; t <= r; t++){ 35 for(int i = sc; i <= c; i++) ans[t][i] = '.'; 36 } 37 } 38 } 39 return false; 40 } 41 42 int main(){ 43 while(scanf("%d%d", &n, &k) && n){ 44 memset(ans, '.', sizeof(ans)); 45 for(int r = 0; r < n; r++) scanf("%s", seat[r]); 46 dfs(0, 'A'); 47 for(int r = 0; r < n; r++){ 48 for(int c = 0; c < n; c++) printf("%c", ans[r][c]); 49 printf(" "); 50 } 51 } 52 return 0; 53 }
总结：
搜索对象的选取很重要，若选取不当，则会运行超时。