hrbust 1283 又见皇后（dfs）

又见皇后

Time Limit: 3000 MS

Memory Limit: 65536 K

Total Submit: 132(37 users)

Total Accepted: 50(29 users)

Rating:

Special Judge: No

Description

国际象棋中，皇后能攻击同一横线、同一竖线、同一斜线（45度）的敌人。

众所周知，有一个非常著名的算法问题，是求在一个n×n的国际象棋棋盘中最多能摆放多少个皇后，使其不能相互攻击。

今天我们暂且不要让问题如此理想化。假设棋盘上有一些障碍物，皇后不能摆在障碍物上，同时也不能穿过障碍物攻击别人。在此条件之下，棋盘上最多又能放多少个皇后？

图中黑色方块表示障碍物，圆点表示皇后

图2是一种最优摆法；图4、图5属于违规摆法

Input

输入包含多组数据。

每组数据的第一行是一个整数n（1≤n≤8），表示棋盘的边长。之后的n行将描述棋盘，其中’X’表示该单元格有障碍物，’.’则表示没有。

n=0表示输入结束。

Output

对于每组数据，请输出一个整数表示最多能在棋盘上放几个皇后，使它们相互不能攻击。
每个答案占一行。

Sample Input

.X..

...X

XXX.

..X.

.X.

X.X

.X.

Sample Output

解题思路：刚开始就是直接dfs里边for循环枚举整个地图上的点，这样会导致很多一直在判断很多已经判断过的点。

其实我们可以这样枚举0-n*n-1 每个值都对应着地图上的一个点，我们只要一直把这个值++，就不会重复判断之前的点了。

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#include<cstring>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define sca(x) scanf("%d",&x)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define inf 0x3f3f3f3f
#define LL long long
#define N 1600
#define inf 0x3f3f3f3f

char a[10][10];
int vis[10][10];
int n,ans;

bool judge(int x,int y)
{
    int tmpx=x,tmpy=y;
    while(tmpx>=0&&a[tmpx][y]!='X')
    {
        if(a[tmpx][y]=='*')return false;
        tmpx--;
    }
    tmpx=x;
    while(tmpx<n&&a[tmpx][y]!='X')
    {
        if(a[tmpx][y]=='*')return false;
        tmpx++;
    }
    while(tmpy>=0&&a[x][tmpy]!='X')
    {
        if(a[x][tmpy]=='*')return false;
        tmpy--;
    }
    tmpy=y;
    while(tmpy<n&&a[x][tmpy]!='X')
    {
        if(a[x][tmpy]=='*')return false;
        tmpy++;
    }
    tmpx=x,tmpy=y;
    while(tmpx>=0&&tmpy<n&&a[tmpx][tmpy]!='X')
    {
        if(a[tmpx][tmpy]=='*')return false;
        tmpx--,tmpy++;
    }
    tmpx=x,tmpy=y;
    while(tmpx>=0&&tmpy>=0&&a[tmpx][tmpy]!='X')
    {
        if(a[tmpx][tmpy]=='*')return false;
        tmpx--,tmpy--;
    }
    tmpx=x,tmpy=y;
    while(tmpx<n&&tmpy<n&&a[tmpx][tmpy]!='X')
    {
        if(a[tmpx][tmpy]=='*')return false;
        tmpx++,tmpy++;
    }
    tmpx=x,tmpy=y;
    while(tmpx<n&&tmpy>=0&&a[tmpx][tmpy]!='X')
    {
        if(a[tmpx][tmpy]=='*')return false;
        tmpx++,tmpy--;
    }
    return true;
}

void Print()
{
    for(int i=0;i<n;i++)
    {
        printf("%s\n",a[i]);
    }
}

void dfs(int now,int step)
{
    if(now>=n*n)
    {
        ans=max(step,ans);
        return ;
    }
    int x=now/n;
    int y=now%n;
    if(a[x][y]=='.'&&judge(x,y))
    {
        a[x][y]='*';
        dfs(now+1,step+1);
        a[x][y]='.';
    }
    dfs(now+1,step);
}
int main()
{
    while(~scanf("%d",&n))
    {
        if(n==0)break;
        for(int i=0;i<n;i++)
        {
            scanf("%s",a[i]);
        }
        ans=0;
        dfs(0,0);
        printf("%d\n",ans);
    }
}
/*
4
.X..
...X
XXX.
..X.
2
XX
.X
3
.X.
X.X
.X.
0
*/

hrbust 1283 又见皇后 （dfs）

相关推荐

hrbust 1283 又见皇后（dfs）