90分求助，#3 TLE

Monkeymonk2006 @ 2024-11-04 23:51:37

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m, ans[100001];
char map[MAXN][MAXN];
bool visited[MAXN][MAXN];
vector<int> _x, _y;
int cnt;

void getPos(int x, int y) {
    if (visited[x][y]) return;
    visited[x][y] = true;
    cnt++;
    if (x + 1 < n && map[x][y] != map[x + 1][y]) {
        getPos(x + 1, y);
    }
    if (x > 0 && map[x][y] != map[x - 1][y]) {
        getPos(x - 1, y);
    }
    if (y + 1 < n && map[x][y] != map[x][y + 1]) {
        getPos(x, y + 1);
    }
    if (y > 0 && map[x][y] != map[x][y - 1]) {
        getPos(x, y - 1);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    }
    for (int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        _x.push_back(t1 - 1); 
        _y.push_back(t2 - 1);
    }

    for (int i = 0; i < m; i++) {
        if (!ans[i]) 
        {
            cnt = 0;
            memset(visited, 0, sizeof(visited));
            getPos(_x[i], _y[i]);            
            ans[i] = cnt;

            for (int j = i + 1; j < m; j++) {
                if (visited[_x[j]][_y[j]]) {
                    ans[j] = ans[i];
                }
            }
        }
        printf("%d\n", ans[i]);
    }
}

by Monkeymonk2006 @ 2024-11-05 16:06:57

更改后AC

//P1141 (NEWER)

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m, ans[100001];
char map[MAXN][MAXN];
int visited[MAXN][MAXN];
vector<int> _x, _y;
int cnt; int flag = 0;

void getPos(int x, int y) {
    if (visited[x][y]) return;
    visited[x][y] = flag;
    cnt++;
    if (x + 1 < n && map[x][y] != map[x + 1][y]) {
        getPos(x + 1, y);
    }
    if (x > 0 && map[x][y] != map[x - 1][y]) {
        getPos(x - 1, y);
    }
    if (y + 1 < n && map[x][y] != map[x][y + 1]) {
        getPos(x, y + 1);
    }
    if (y > 0 && map[x][y] != map[x][y - 1]) {
        getPos(x, y - 1);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    }
    for (int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        _x.push_back(t1 - 1);
        _y.push_back(t2 - 1);
    }

    for (int i = 0; i < m; i++) 
    {
        if (!visited[_x[i]][_y[i]])
        {
            flag++;
            getPos(_x[i], _y[i]);
            ans[flag] = cnt;
            printf("%d\n", cnt);
            cnt = 0;
        }
        else
        {
            printf("%d\n", ans[visited[_x[i]][_y[i]]]);
        }

    }
}