思路：每次找出可能情况最少的位置枚举可能情况！！！
poj2676和这题一样不过poj数据比较水，很容易过。
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define M 100005
using namespace std;
char str[][];
struct point
{
int x,y;
}p[];
int cnt,tot;
bool is_ok(int x,int y,char c) //判断c是否可以放
{
int u=x/*;
int v=y/*;
for(int i=;i<;i++) //3x3的小格子
for(int j=;j<;j++)
if(str[u+i][v+j]==c) return ;
for(int i=;i<;i++) //行和列
if(str[i][y]==c||str[x][i]==c) return ;
return ;
}
void find_best_way(int &x,int &y) //找出可能情况最少的位置
{
int best=;
for(int i=;i<cnt;i++){
if(str[p[i].x][p[i].y]!='.') continue;
int num=;
for(char j='';j<='';j++)
if(is_ok(p[i].x,p[i].y,j)) num++;
if(num<best) x=p[i].x,y=p[i].y,best=num;
}
}
bool dfs()
{
if(tot==){
for(int i=;i<;i++){
for(int j=;j<;j++)
printf("%c",str[i][j]);
printf("\n");
}
return ;
}
int x,y;
find_best_way(x,y);
tot--;
for(char j='';j<='';j++){
if(is_ok(x,y,j)){
str[x][y]=j;
if(dfs()) return ;
}
}
tot++;
str[x][y]='.';
return ;
}
int main()
{
int t,ca=,n,m,a;
scanf("%d",&t);
while(t--){
cnt=;
for(int i=;i<;i++){
scanf("%s",str[i]);
for(int j=;j<;j++)
if(str[i][j]=='.'){
p[cnt].x=i;
p[cnt++].y=j;
}
}
tot=cnt;
printf("Case %d:\n",++ca);
dfs();
}
return ;
}