[code language=”cpp”]

#include<iostream>

using namespace std;

char map[4][4];
int n, maxNum;
bool CanPut(int row, int col)
{
int i;
if (map[row][col] == ‘X’) return false;
for(i = row – 1; i >= 0; –i)
{
if (map[i][col] == ‘O’) return false;
if (map[i][col] == ‘X’) break;
}
for(i = col – 1; i >= 0; –i)
{
if (map[row][i] == ‘O’) return false;
if (map[row][i] == ‘X’) break;
}
return true;
}

void Solve(int curNum, int position)
{
if(position == n*n)
{
if (curNum > maxNum)
{
maxNum = curNum;
return;
}
}

else
{
int row = position/n;
int col = position%n;
if(CanPut(row, col)==true)
{
map[row][col] = ‘O’;
Solve(curNum + 1, position + 1);
map[row][col] = ‘.’;
}
Solve(curNum,position+1);
}
}
int main()
{
int i,j;
while(cin>>n && n != 0)
{
for(i=0; i<n; i++)
{
for(j=0; j<n; j++) cin >> map[i][j];
}
maxNum = 0;
Solve(0,0);
cout<<maxNum<<endl;
}
return 0;
}

[/code]

类似八皇后问题,使用了递归和回溯。

Leave a comment

Your email address will not be published. Required fields are marked *

www.000webhost.com