链接：
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 ;
}
总结：
搜索对象的选取很重要，若选取不当，则会运行超时。