0分求助

P1141 01迷宫

Hzj201014 @ 2024-02-02 16:13:51

#include<bits/stdc++.h>
using namespace std;
#pragma G++ optimize(2)
char dt[1005][1005];
int n,m,x,y,ans[405][405],t,ditu[1005][1005];
int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct node{
    int x,y,r;
};
queue<node>que;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            cin>>dt[i][j];
            ditu[i][j] = dt[i][j] - '0';
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            ans[i][j] = -1;
        }
    }
    for(int k = 1;k <= m;k++){
        t = 0;
        cin>>x>>y;
        node a = {x,y,0};
        que.push(a);
        ans[x][y] = 0;
        while(!que.empty()){
            int X = que.front().x,Y = que.front().y;
            for(register int i = 0;i < 4;i++){
                int newx = X + d[i][0],newy = Y + d[i][1];
                if(newx >= 1 && newx <= n && newy >= 1 && newy <= n&& ans[newx][newy] == -1){
                    a = {newx,newy,que.front().r + 1};
                    que.push(a);
                    ans[newx][newy] = que.front().r + 1;
                }
            }
            que.pop();
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                if(ans[i][j] != -1){
                    t++;
                }
            }
        }
        cout<<t<<'\n';
    }
    return 0;
}

半天查不出来错,各位大佬帮看一下


by yangzishuo0418 @ 2024-02-09 12:35:31

你有没有想过每次 bfs 时都要清空一次的事情?


by yangzishuo0418 @ 2024-02-09 12:36:48

没清空的话你没法判断那个点你有没有踩过


by yangzishuo0418 @ 2024-02-09 12:38:18

应该在第 52 行之后插入 memset(ans,-1,sizeof a) (尽管这样可能会超时)


by masonxiong @ 2024-02-09 22:40:32

显然,这个程序复杂度就不对

如果迷宫是一个所有格子互相可达的图,那么一次搜索的时间可以达到 O(n^2),那么对于整体而言,复杂度会达到 O(n^2m)

鉴于 n 的极限是 10^3m 的极限是 10^5,则你的程序的运算次数将达到 10^{11} 量级,而且并未计算常数,又因为计算机运行速度(CPU 主频)大概在 4GHz(4\times10^9) 左右,因此此程序会 TLE, 无法通过

而且,你每次 BFS 时的 ans 数组并未初始化,导致结果肯定就不对,直接 WA

另,你需要知道,register 关键字已经弃用了,而 Luogu 有 O2 优化选项,#pragma G++ optimize(2) 没必要,std::queue 又是对 std::deque 的封装,后者常数极大,解绑优化在小规模输入时也没有用处,你这优化了也和没优化一样

正确的解法是,鉴于此迷宫可被看为一个无向图,也就是说,若 A 能到 B,则 B 一定能到 A(显然),那么一个连通分量内的答案都是相等的,也就是这个联通分量的大小。

求解这个可以使用 Tarjan 算法,当然这太大材小用,我们只需要进行多次 DFS 查找全部连通分量即可。

此算法时间复杂度可以达到 O(n),完全可以通过这题。我就是用的这个解法 AC 的(


|