4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0

 1 #include <iostream>
 2 
 3 using namespace std;
 4 char a[5][5];
 5 int cnt,n;
 6 bool judge(int x,int y)   //判断这一步可不可以走
 7 {
 8     if(a[x][y]==‘X‘)
 9         return 1;
10     if(a[x][y]==‘*‘)
11         return 1;
12     int i;
13     //判断这一行上有无碉堡
14     for(i=y;i>=1;i--){
15         if(a[x][i]==‘*‘)
16             return true;
17         if(a[x][i]==‘X‘)
18             break;
19     }
20     for(i=y;i<=n;i++){
21         if(a[x][i]==‘*‘)
22             return true;
23         if(a[x][i]==‘X‘)
24             break;
25     }
26     //判断这一列上有无碉堡
27     for(i=x;i>=1;i--){
28         if(a[i][y]==‘*‘)
29             return 1;
30         if(a[i][y]==‘X‘)
31             break;
32     }
33     for(i=x;i<=4;i++){
34         if(a[i][y]==‘*‘)
35             return 1;
36         if(a[i][y]==‘X‘)
37             break;
38     }
39     //可以走
40     return 0;
41 }
42 void dfs(int cx,int cy,int cn)
43 {
44     if(cn>cnt) cnt=cn;    //记录最大值
45     int x=-1,y=-1;
46     int i,j;
47     for(i=cx;i<=n;i++)   //选择这一步的位置
48         for(j=1;j<=n;j++){
49             if(i==cx && j<=cy)
50                 continue;
51             if(judge(i,j))
52                 continue;
53             x=i;y=j;
54             a[x][y] = ‘*‘;
55             dfs(x,y,cn+1);
56             a[x][y] = ‘.‘;
57         }
58     if(x==-1 && y==-1)
59         return ;
60 }
61 int main()
62 {
63     while(cin>>n){
64         if(n==0) break;
65         int i,j;
66         for(i=1;i<=n;i++)   //输入地图
67             for(j=1;j<=n;j++)
68                 cin>>a[i][j];
69         cnt = 0;
70         dfs(1,0,0);  //深搜
71         cout<<cnt<<endl;
72     }
73     return 0;
74 }