在一个N*N的棋盘上,有一些墙,我们用X表示。
现在,你可以在棋盘上表示为“点”的地方,即"."的地方放一些棋子。但是,必须满足:
1.放这个棋子的地方必须是"."
2.这个地方的横纵不可以有其它棋子
3.如果这个地方的横纵有其它棋子,但是有墙把它们隔开,那么此处还是可以放棋子。
拿样例来举例,有如图这些方法(可能不止这些)
其中能放的最多棋子的图为5(而且找不出能放更多棋子的方案)。
现在,给你一个棋盘,请问,能在上面按上述规则放最多多少棋子
- 输入
-
数字N(1<=N<=4)
接着一个N*N的棋盘
数据以N=0结尾
- 输出
-
能放棋子的最大值
- 样例输入
-
4 .X.. .... XX.. ....
- 样例输出
-
5
#include <iostream> using namespace std; char data[10][10]; int a[10][10]; //0-free 1-done 2-forbidden -1-wall int ma, num; void cal(int n, int x, int y) { int i, j; for(i = x-1; i >= 0; i --) { if(a[i][y] == -1) break; if(a[i][y] == 0) a[i][y] = 2; else if(a[i][y] == 2) a[i][y] = 3; } for(i = x+1; i < n; i ++) { if(a[i][y] == -1) break; if(a[i][y] == 0) a[i][y] = 2; else if(a[i][y] == 2) a[i][y] = 3; } for(i = y-1; i >= 0; i --) { if(a[x][i] == -1) break; if(a[x][i] == 0) a[x][i] = 2; else if(a[x][i] == 2) a[x][i] = 3; } for(i = y+1; i < n; i ++) { if(a[x][i] == -1) break; if(a[x][i] == 0) a[x][i] = 2; else if(a[x][i] == 2) a[x][i] = 3; } for(i = 0; i < n; i ++) for(j = 0; j < n; j ++) if(a[i][j] == 0) { ++num; if(num > ma) ma = num; a[i][j] = 1; cal(n, i, j); a[i][j] = 0; --num; } for(i = x-1; i >= 0; i --) { if(a[i][y] == -1) break; if(a[i][y] == 3) a[i][y] = 2; else if(a[i][y] == 2) a[i][y] = 0; } for(i = x+1; i < n; i ++) { if(a[i][y] == -1) break; if(a[i][y] == 2) a[i][y] = 0; else if(a[i][y] == 3) a[i][y] = 3; } for(i = y-1; i >= 0; i --) { if(a[x][i] == -1) break; if(a[x][i] == 2) a[x][i] = 0; else if(a[x][i] == 3) a[x][i] = 2; } for(i = y+1; i < n; i ++) { if(a[x][i] == -1) break; if(a[x][i] == 2) a[x][i] = 0; else if(a[x][i] == 3) a[x][i] = 2; } } int main() { int n; int i, j; while(1) { num = ma = 0; cin >> n; if(n == 0) break; for(i = 0; i < n; i ++) { cin >> data[i]; for(j = 0; j < n; j ++) if(data[i][j] == '.') a[i][j] = 0; else a[i][j] = -1; } for(i = 0; i < n; i ++) { for(j = 0; j < n; j ++) if(a[i][j] == 0) { num ++; if(num > ma) ma = num; a[i][j] = 1; cal(n, i, j); a[i][j] = 0; -- num; } } cout << ma << '\n'; } return 0; }