洛谷 1141_01迷宫_bfs

发布于 2019-05-05  10 次阅读


题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上,那么你可以移动到相邻4格中的某一格1上,同样若你位于一格1上,那么你可以移动到相邻4格中的某一格0上。

你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身


思路

一开始打了一个暴力广搜,然后超时了70分
后面发现可以之做一边,把每一部分可以走到的格数先算出来,再输出就可以了


#include 
#include 
#include 
using namespace std;
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int a[1001][1001],ans,t=0;
int f[1000001],fl[1001][1001],n,m;
int bfs(int x,int y)
{
    queue tx;
    queue ty;
    tx.push(x);
    ty.push(y);
    fl[x][y]=t;
    while (!tx.empty())
    {
        int xx=tx.front(),yy=ty.front();
        tx.pop(); ty.pop();
        for (int i=1;i<=4;i++)
            if (xx+dx[i]>=1&&xx+dx[i]<=n&&yy+dy[i]>=1&&yy+dy[i]<=n&&a[xx+dx[i]][yy+dy[i]]!=a[xx][yy]&&fl[xx+dx[i]][yy+dy[i]]==0)
            {
                tx.push(xx+dx[i]);
                ty.push(yy+dy[i]);
                fl[xx+dx[i]][yy+dy[i]]=t;
                ans++;
            }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        char ch[1001];
        scanf("%s",ch);
        for (int j=0;j
]]>