80分求调

P1141 01迷宫

rish @ 2024-08-25 23:30:44

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
const int NN = 1e5+10;
int f[N][N], a[N][N], vis[N][N], n, m, xx, yy;
pair<int, int> fa[N][N];
int dx[6] = {0, 1, -1, 0, 0};
int dy[6] = {0, 0, 0, 1, -1};
void bfs(int x, int y)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) vis[i][j] = 0;
    vis[x][y] = 1;
    pair<int, int> q[NN];
    int h=1, t=0;
    q[++t] = {x, y};
    while(h<=t)
    {
        int nx = q[h].first, ny = q[h++].second;
        for(int i=1;i<=4;i++)
            if(dx[i]+nx<1||dx[i]+nx>n||dy[i]+ny<1||dy[i]+ny>n) continue;
            else if(a[dx[i]+nx][dy[i]+ny]!=a[nx][ny]&&!vis[dx[i]+nx][dy[i]+ny]) 
                f[x][y]++, vis[dx[i]+nx][dy[i]+ny] = 1, q[++t] = {dx[i]+nx,dy[i]+ny}, fa[dx[i]+nx][dy[i]+ny] = {x, y};
    }
    f[x][y]++;
}
int main()
{
    string s;
    cin >> n >> m;
    getline(cin, s);
    for(int i=1;i<=n;i++)
    {
        getline(cin, s);
        for(int j=0;j<n;j++) a[i][j+1] = s[j]-'0';
    } 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) fa[i][j] = {i, j};
    for(int i=1;i<=m;i++)
    {
        cin >> xx >> yy;
        if(!f[fa[xx][yy].first][fa[xx][yy].second]) bfs(xx, yy);
        cout << f[fa[xx][yy].first][fa[xx][yy].second] << endl;
    }
    return 0;
}

by XVETV6 @ 2024-08-26 00:48:24

  1. NN 小了,开1e6+10
  2. 把 pair<int, int> q[NN]; 移到bfs外面。否则每次进入都会创建 NN 大小的数组,消耗 O(NN) 的时间。\ 至于不清空q的正确性:每次都是先入队,再取队首。每次入队会覆盖上次bfs残留的数据,所以q数组不用清空
  3. bfs 里不用清空vis,因为同一个连通块不会重复进入

by rish @ 2024-08-26 09:50:14

@XVETV6 过了,感谢感谢!!


|