简单深搜,可以完全暴力,不会超时的。
#include<iostream> #include<cstring> #include<cmath> using namespace std; #define MAX(a,b) (a>b?a:b) char maze[10][10]; int n, maxn; void DFS(int step,int count); int cheak(int x, int y); int main() { int i; while(scanf("%d",&n), n) { maxn = 0; for(i = 0; i < n; i++) scanf("%s",maze[i]); DFS(0,0); printf("%d\n",maxn); } return 0; } void DFS(int step,int count) { int x, y; maxn = MAX(maxn,count); if(step == n*n) return ; x = step/n; y = step%n; if(maze[x][y] == ‘.‘ && cheak(x,y)) { maze[x][y] = ‘O‘; DFS(step+1,count+1); maze[x][y] = ‘.‘; } DFS(step + 1, count); } int cheak(int x, int y) { int i; for(i = x-1; i >= 0; i--) { if(maze[i][y] == ‘O‘) return 0; else if(maze[i][y] == ‘X‘) break; } for(i = y-1; i >= 0; i--) { if(maze[x][i] == ‘O‘) return 0; else if(maze[x][i] == ‘X‘) break; } return 1; }