#include<iostream>
using namespace std;
int n,Max,C[4][4];
char board[5][5];
bool vis[16];
bool isok(int x,int y)
{
for (int i = x + 1; i < n && board[i][y] != 'X'; i++)
if(board[i][y] == '0')
return false;
for (int i = x - 1; i >= 0 && board[i][y] != 'X'; i--)
if(board[i][y] == '0')
return false;
for (int i = y; i < n && board[x][i] != 'X'; i++)
if (board[x][i] == '0')
return false;
for (int i = y - 1; i >= 0 && board[x][i] != 'X'; i--)
if (board[x][i] == '0')
return false;
return true;
}
void dfs(int num)
{
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
if (board[i][j]=='.'&&isok(i,j))
{
board[i][j]='0';
dfs(num+1);
board[i][j]='.';
}
}
}
if (num>Max) Max=num;
}
int main()
{
while (cin>>n&&n)
{
for (int i=0;i<n;i++)
cin>>board[i];
Max=0;
dfs(0);
cout<<Max<<endl;
}
return 0;
}
回溯法還是不熟練,參考了一下網上别的童鞋的代碼才AC的,要多加練習!