POJ1111【BFS】

在搜1011的时候误搜了1111，简单BFS吧，多一个X就是多四个面，每次看看他的四个面有多少个重复的，然后剪掉，最后答案加上就好了；

code：

//#include <bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<queue>

#include<math.h>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

char ma[25][25];

int n,m,sx,sy;

struct asd{

    int x,y;

};

bool vis[25][25];

int dx[8]={0,0,-1,1,-1,1,1,-1};

int dy[8]={-1,1,0,0,-1,1,-1,1};

int BFS()

{

    int ans=0;

    asd now,nex;

    memset(vis,0,sizeof(vis));

    queue<asd>q;

    now.x=sx-1;

    now.y=sy-1;

    vis[now.x][now.y]=true;

    q.push(now);

    while(!q.empty())

    {

        now=q.front();q.pop();

        int temp=4;

        for(int i=0;i<8;i++)

        {

            int xx=now.x+dx[i];

            int yy=now.y+dy[i];

            if(ma[xx][yy]=='.'||xx<0||yy<0||xx>=n||yy>=m)

                continue;

            if(i<4&&ma[xx][yy]=='X')

                temp--;

            if(vis[xx][yy]) continue;

            vis[xx][yy]=1;

            nex.x=xx;

            nex.y=yy;

            q.push(nex);

        }

//        printf("%d\n",temp);

        ans+=temp;

    }

    return ans;

}

int main()

{

    while(~scanf("%d%d%d%d",&n,&m,&sx,&sy))

    {

        if(!n&&!m&&!sx&&!sy) break;

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

            scanf("%s",ma[i]);

        printf("%d\n",BFS());

    }

    return 0;

}

巴特西

POJ1111【BFS】

最新文章

热门文章