经典深搜。注意满足条件。
#include <stdio.h>
#include <string.h> #define MAXNUM 5 char map[MAXNUM][MAXNUM];
int visit[MAXNUM][MAXNUM]; int chk(int row, int col, int n) {
int i, k; if (row< || row>=n || col< || col>=n )
return ;
if (visit[row][col] || map[row][col]!='.')
return ; // if this position is valid or not
k = ;
for (i=col-; i>=; --i) {
if (map[row][i] == 'X')
break;
if (map[row][i] == '.' && visit[row][i]) {
k = ;
break;
}
}
if (k) return ; for (i=col+; i<n; ++i) {
if (map[row][i] == 'X')
break;
if (map[row][i] == '.' && visit[row][i]) {
k = ;
break;
}
}
if (k) return ; for (i=row-; i>=; --i) {
if (map[i][col] == 'X')
break;
if (map[i][col] == '.' && visit[i][col]) {
k = ;
break;
}
}
if (k) return ; for (i=row+; i<n; ++i) {
if (map[i][col] == 'X')
break;
if (map[i][col] == '.' && visit[i][col]) {
k = ;
break;
}
} if (k)
return ;
else
return ;
} int dfs(int n) {
int i, j, tmp, max = ; for (i=; i<n; ++i) {
for (j=; j<n; ++j) {
if ( chk(i, j, n) ) {
visit[i][j] = ;
tmp = dfs(n) + ;
if (tmp > max)
max = tmp;
visit[i][j] = ;
}
}
} return max;
} int main() {
int n, amount;
int i; while (scanf("%d", &n)!=EOF && n) {
getchar();
for (i=; i<n; ++i)
gets(map[i]); memset(visit, , sizeof(visit));
amount = dfs(n);
printf("%d\n", amount);
} return ;
}