HDU 1045 (DFS搜索)

时间：2021-06-15 16:44:34

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1045

题目大意：在不是X的地方放O，所有O在没有隔板情况下不能对视（横行和数列），问最多可以放多少个O。

解题思路：

题目规模比较小（4*4），可以DFS解决。

对于一个点，要么放，要么不放。

放的话条件必须是上下左右四个方向扫到边界且不首先碰到X。

可以只对放的点进行标记，而对于不放的点不进行标记，这样当dep>n*n的时候及时return就行了。

注意每次dfs只需要按顺序考虑一个点，而不要同时对整个棋盘所有非X点同时dfs，否则就爆了。

原因是，每次只关联一个点，其它点都是不关联的，如果dfs等于做了大量重复计算。

#include "cstdio"

#include "string"

#include "cstring"

#include "iostream"

using namespace std;

int n,vis[][],ans;

char map[][];

struct status

{

    int x,y;

    char type;

    status(int x,int y,char type):x(x),y(y),type(type) {}

    status() {}

}P[];

bool judge(int X,int Y)

{

    if(map[X][Y]=='X') return false;

    for(int i=X-; i>=&&map[i][Y]!='X'; i--)  if(vis[i][Y]) return false;

    for(int i=X+; i<=n&&map[i][Y]!='X'; i++) if(vis[i][Y]) return false;

    for(int i=Y-; i>=&&map[X][i]!='X'; i--) if(vis[X][i]) return false;

    for(int i=Y+; i<=n&&map[X][i]!='X'; i++)   if(vis[X][i]) return false;

    return true;

}

void dfs(int p,int s)

{

    if(p>n*n) {ans=max(ans,s);return;}

    dfs(p+,s);

    vis[P[p].x][P[p].y]=true;

    if(judge(P[p].x,P[p].y)) dfs(p+,s+);

    vis[P[p].x][P[p].y]=false;

}

int main()

{

    //freopen("in.txt","r",stdin);

    ios::sync_with_stdio(false);

    string tt;

    while(cin>>n&&n)

    {

        memset(vis,,sizeof(vis));

        int cnt=;ans=;

        for(int i=;i<=n;i++)

        {

            cin>>tt;

            for(int j=;j<tt.size();j++)

            {

                P[++cnt]=status(i,j+,tt[j]);

                map[i][j+]=tt[j];

            }

        }

        dfs(,);

        cout<<ans<<endl;

    }

}
11909497 2014-10-19 11:59:35 Accepted 1045 0MS 292K 1335 B C++ Physcal

相关文章