1045--Fire Net

原题链接

http://acm.hdu.edu.cn/showproblem.php?pid=1045

Sample Input
4
.X..
….
XX..
….
2
XX
.X
3
.X.
X.X
.X.
3
…
.XX
.XX
4
….
….
….
….
0

Sample Output
5
1
5
2
4

解题思路

首先这个是八皇后的高级变形问题。
起初我也是按八皇后的思路在想，可就是想不明白，于是换种思路，对每个格子进行试探，试探之后，然后判断这个格子能不能放，一共也就16个格子，

代码

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 5;
char ma[maxn][maxn];
int n,cnt,maxx;
//判断此位置放了之后，冲不冲突
int isTrue(int x, int y)
{
    //向上检测
    for(int i=y; i>-1; --i)
    {
        if(ma[x][i] == '1')
            return 0;
        if(ma[x][i] == 'X')
            break;
    }
    //向下检测
    for(int i=y; i<n; ++i)
    {
        if(ma[x][i] == '1')
            return 0;
        if(ma[x][i] == 'X')
            break;
    }
    //向左检测
    for(int i=x; i>-1; --i)
    {
        if(ma[i][y] == '1')
            return 0;
        if(ma[i][y] == 'X')
            break;
    }
    for(int i=x; i<n; ++i)
    {
        if(ma[i][y] == '1')
            return 0;
        if(ma[i][y] == 'X')
            break;
    }
    return 1;
}
void dfs()
{
   if(cnt > maxx)
    maxx = cnt;
   for(int x=0; x<n; ++x)
   {
       for(int y=0; y<n; ++y)
       {
           if(ma[x][y] == 'X' || ma[x][y] == '1')
                continue;
           if(!isTrue(x,y))
                continue;
           cnt++;
           ma[x][y] = '1';
           dfs();
           cnt--;
           ma[x][y] = '.';
       }
   }

}
int main()
{
    while(cin >> n)
    {
        if(!n)
            break;
        cnt = 0,maxx = 0;
        for(int i=0; i<n; ++i)
            cin >> ma[i];
        dfs();
        cout << maxx <<endl;
    }

    return 0;
}