求调

P1141 01迷宫

dongrunxuan @ 2023-12-14 20:34:42


#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int a[maxn][maxn];
bool vis[maxn][maxn];
int ans[maxn][maxn];
int dx[5]={0,0,1,-1,0};
int dy[5]={0,1,0,0,-1};
int bx,by;
int n,m;
struct node
{
    int x,y;
};
bool can(int x,int y)
{
    if(x<1||y<1||x>n||y>n)
    {
        return 0;
    }
    if(vis[x][y]==1)
    {
        return 0;
    }
    return 1;
}
int bfs(node now)
{
    int ans=1;
    queue<node> qu;
    qu.push(now);
    while(!qu.empty())
    {
        now=qu.front();
        qu.pop();
        for(int i=1;i<=4;i++)
        {
            int nx=now.x+dx[i];
            int ny=now.y+dy[i];
            if(can(nx,ny))
            {
                node next;
                next.x=nx;
                next.y=ny;
                ans++;
                vis[nx][ny]=1;
                qu.push(next);          
            }

        }
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char c;
            cin>>c;
            if(c=='0')
            {
                a[i][j]=0;
            }
            else
            {
                a[i][j]=1;
            }
        }
    }
    while(m--)
    {
        memset(vis,0,sizeof(vis));
        cin>>bx>>by;
        vis[bx][by]=1;
        node now;
        now.x=bx;
        now.y=by;
        int ans=bfs(now);
        cout<<ans<<endl;
    }
    return 0;
}

by zjpwdyf @ 2023-12-14 20:51:44

您有没有想过 getchar() 会读入换行符(\n)


by zjpwdyf @ 2023-12-14 20:52:51

而且您的代码时间复杂度高达 O(n^2m),会TLE


|