求解#1超时但是自测正确

P1141 01迷宫

HBQS @ 2024-12-25 20:45:58

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int maxn = 1010;
int mp[maxn][maxn],xx[]={0,0,1,-1},yy[]={1,-1,0,0};
int vis[maxn][maxn];
void bfs();
queue<int>x;
queue<int>y;
int h,n,a,b,cnt;
int main()
{
    char ch;
    cin>>h>>n;
    for(int i = 1;i<=h;i++)
    {
        for(int j = 1;j<=h;j++)
        {
            cin>>ch;
            mp[i][j] = ch-'0';
        }
    }
    for(int i = 0;i<n;i++)
    {
        cin>>a>>b;
        x.push(a);
        y.push(b);
        vis[a][b] = 1;
        cnt=0;
        bfs();
        for(int j = 1;j<=h;j++)
        {
            for(int k = 1;k<=h;k++)
            {
                if(vis[j][k]) cnt++;
            }
        }
        cout<<cnt<<endl;
        memset(vis,0,sizeof(vis));
    }
}
void bfs()
{
    while(!x.empty())
    {
        int cx = x.front();
        int cy = y.front();
        x.pop(),y.pop();
        for(int i = 0;i<4;i++)
        {
            int dx = cx + xx[i];
            int dy = cy + yy[i];
            if(dx>=1&&dy>=1&&dx<=h&&dy<=h&&!vis[dx][dy])
            {
                vis[dx][dy] = 1;
                x.push(dx);
                y.push(dy);
            }
        }
    }
}
/*written by HBQS!*/

这个代码一定会超时 但为什么会wa呢?本来想着看看能拿多少分再优化 结果没超时的都wa了 求救 思路是先起点广搜 将搜过的地方都标记 然后再遍历这个数组 每经历过一个地方就计数器加1


by HBQS @ 2024-12-25 20:54:04

哦 犯病了 要补充一个mp[dx][dy]!=mp[cx][cy] 这下就只剩超时优化了


by HBQS @ 2024-12-25 21:07:00

12.25,21:06ac了 撒花花


|