做bfs总是RE,有没有大佬解释解释

P1141 01迷宫

kendas @ 2024-12-21 20:40:04

做bfs的题总是会RE,这到底是为什么,按理说队列中最多也就是把整个图的点加入啊,为什么会RE呢,想不明白,像这题绝大多都RE了,就30分,然后队列开大一点就MLE

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int n,Q;
char g[N][N];
bool st[N][N];
int blocks[N][N];
PII f[N*N];
int tt = -1,hh;
int dx[]{-1,0,1,0},dy[]{0,1,0,-1};

void bfs(int x,int y)
{
    f[++ tt] = {x,y};
    int step = 0;
    while(hh <= tt)
    {
        auto t = f[hh ++];
        st[t.first][t.second] = true;
        for(int i = 0; i < 4; i ++)
        {
            int tx = t.first + dx[i], ty = t.second + dy[i];
            if(!st[tx][ty] && tx >= 1 && tx <= n && ty >= 1 && ty <= n && g[tx][ty] == (g[t.first][t.second] ^ 1))
            {
                f[++ tt] = {tx,ty};
            }
        }

    }
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
            if(st[i][j])step ++;
    }
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(st[i][j])blocks[i][j] = step;
}

int main()
{
    cin>>n>>Q;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin>>g[i][j];
    while(Q --)
    {
        int x,y;cin>>x>>y;
        if(blocks[x][y])cout << blocks[x][y] << endl;
        else bfs(x,y),cout << blocks[x][y] << endl;
    }
}

by kendas @ 2024-12-24 14:52:37

找到原因了,因为没有及时把tx,ty点设置为已访问,优化了很多,但是还是有个倔强的#3不给我过QAQ

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int n,Q;
char g[N][N];
bool st[N][N];
int blocks[N][N];
PII f[N*N];
int tt = -1,hh;
int dx[]{-1,0,1,0},dy[]{0,1,0,-1};
vector<PII>mem;
void bfs(int x,int y)
{
    memset(st,false,sizeof st);
    hh = 0, tt = -1;
    f[++ tt] = {x,y};
    int step = 1;
    st[x][y] = true;
    mem.push_back({x,y});
    while(hh <= tt)
    {
        auto t = f[hh ++];
        for(int i = 0; i < 4; i ++)
        {
            int tx = t.first + dx[i], ty = t.second + dy[i];
            if(!st[tx][ty] && tx >= 1 && tx <= n && ty >= 1 && ty <= n && g[tx][ty] == (g[t.first][t.second] ^ 1))
            {
                st[tx][ty] = true;
                step ++;
                mem.push_back({tx,ty});
                f[++ tt] = {tx,ty};
            }
        }

    }
    for(auto t : mem)
    {
        blocks[t.first][t.second] = step;
    }
    mem.clear();
}

int main()
{
    cin>>n>>Q;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin>>g[i][j];
    while(Q --)
    {
        int x,y;cin>>x>>y;
        if(blocks[x][y])cout << blocks[x][y] << endl;
        else bfs(x,y),cout << blocks[x][y] << endl;
    }
}

by kendas @ 2024-12-24 15:09:00

@kendas 这下真过了,此贴结了,找到了原因,#3的数据有点坑,大量询问,而且每次询问都是没有被bfs过的点,导致很多memset操作,浪费了很多时间,实际上不需要memset st数组