萌新70分吐血暴毙求助!!

P1141 01迷宫

THJAC @ 2024-07-25 15:31:41

已老实,求放过

#include<bits/stdc++.h>

#define IOS; ios :: sync_with_stdio(false);

using namespace std;    

const int N = 1e3 + 010;

struct node {
    int x, y;
};

int ans = 1;
int n, m;
char a[N][N];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int vis[N][N];

void bfs (int xx, int yy) {
    queue<node> q;
    q.push ({xx, yy});
    vis[xx][yy] = 1;
    while (!q.empty ()) {
        auto t = q.front ();
        q.pop();
        int x = t.x;
        int y = t.y;
        //cout << x << ' ' << y << endl;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 1 and ny >= 1 and nx <= n and ny <= n and vis[nx][ny] == 0 and a[x][y] != a[nx][ny]) {
                vis[nx][ny] = 1;
                q.push ({nx, ny});
                //cout << nx << ' ' << ny << endl;
                ++ans;
            }
        }
    }
    return;
}

int main () {
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    while (m--) {
        int i, j;
        cin >> i >> j;
        memset (vis, 0, sizeof (vis));
        bfs (i, j);
        cout << ans << endl;
        ans = 1;
    }
    return 0;
}

by lunjiahao @ 2024-07-25 15:54:10

@THJAC 请使用记忆化,读一组数据跑一次图会超时


by West0319 @ 2024-08-05 14:29:39

同样70分的我


|