P1141 01迷宫

题目描述

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

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入输出格式

输入格式：

输入的第1行为两个正整数n，m。

下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。

接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出格式：

输出包括m行，对于每个询问输出相应答案。

输入输出样例

输入样例#1：

2 2

1 1

2 2

输出样例#1：

说明

所有格子互相可达。

对于20%的数据，n≤10；

对于40%的数据，n≤50；

对于50%的数据，m≤5；

对于60%的数据，n≤100，m≤100；

对于100%的数据，n≤1000，m≤100000。

思路:

　　bfs,dfs均可.但是我用的是bfs

坑点:

　　在进行bfs时要将当前状态与扩展出的状态进行比较,而不是将起点状态与被扩展出的多个状态进行比较...QwQ被坑在这里,一直不对...

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int M = ;

int n,m,cannot;

int dx[] = {,,-, },

    dy[] = {,, ,-};

int jz[M][M],ans[M][M];

string s;

bool v[M][M];

struct A{

    int nx,ny;

}dad[M][M];

bool can(int x1,int y1,int x2,int y2)

{

    if( x1< || x1>n || y1< || y1>n || v[x1][y1] || jz[x1][y1] + jz[x2][y2] != )

        return ;

    return ;

}

void ask(int x,int y)

{

    A pre;

    A now;

    cannot = jz[x][y];

    int cnt=;

    queue<A>q;

    pre.nx=x;

    pre.ny=y;

    q.push(pre);

    v[x][y]=;

    dad[x][y].nx=x;

    dad[x][y].ny=y;

    while(!q.empty())

    {

        now=q.front();

        q.pop();

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

        {

            pre.nx=now.nx+dx[i],pre.ny=now.ny+dy[i];

            if(can(pre.nx,pre.ny,now.nx,now.ny))

            {

                cnt++;

                q.push(pre);

                v[pre.nx][pre.ny]=;

                dad[pre.nx][pre.ny].nx=x,dad[pre.nx][pre.ny].ny=y;

            }

        }

    }

    ans[x][y]=cnt;

}

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        cin>>s;

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

        {

            jz[i][j]=s[j-]-'';

        }

    }

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

    {

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

        {

            if(!v[i][j])

                ask(i,j);

        }

    }

    /*

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

     for(int j=1;j<=n;j++)

        printf("%d ",ans[i][j]);

    printf("\n");

    */

    for(int i=,x,y;i<m;i++)

    {

        scanf("%d%d",&x,&y);

        printf("%d\n",ans[dad[x][y].nx][dad[x][y].ny]);

    }

    return ;

}

巴特西

luogu P1141 01迷宫 x

P1141 01迷宫

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章