优化前7AC 3TLE 3.65s / 24.66MB

#include<bits/stdc++.h>
using namespace std;
#define N 1010
bool mp[N][N], vis[N][N];
int xx, yy;
int ans, n, m;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
void dfs(int x, int y) {
    ans++;
    vis[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int sx = x + dx[i], sy = y + dy[i];
        if (sx >= 1 && sx <= n && sy >= 1 && sy <= n && mp[sx][sy] != mp[x][y] && !vis[sx][sy]) dfs(sx, sy);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
        char c;
        cin >> c;
        mp[i][j] = c - '0';
    }
    for (int i = 1; i <= m; i++) {
        memset(vis, 0, sizeof(vis));
        ans = 0;
        cin >> xx >> yy;
        dfs(xx, yy);
        cout << ans << endl;
    }
    return 0;
}

利用数组优化后 7AC 3TLE 3.67s / 33.38MB
反而更慢了

#include<bits/stdc++.h>
using namespace std;
#define N 1010
bool mp[N][N], go[N][N][3][3], vis[N][N];
int ans, n, m, xx, yy;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
void dfs(int x, int y) {
	ans++;
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int sx = x + dx[i], sy = y + dy[i];
		if (!vis[sx][sy] && go[x][y][dx[i] + 1][dy[i] + 1]) dfs(sx, sy);
	}
}
int main() {
	#ifndef ONLINE_LUDGE
		freopen("729.in", "r", stdin);
		freopen("729.out", "w", stdout);
	#endif
	cin >> n >> m;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
		char c;
		cin >> c;
		mp[i][j] = c - '0';
	}
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 0; k < 4; k++) {
		int sx = i + dx[k], sy = j + dy[k];
		if (mp[sx][sy] == !mp[i][j] && sx >= 1 && sx <= n && sy >= 1 && sy <= n) go[i][j][dx[k] + 1][dy[k] + 1] = true;
	}
	for (int i = 1; i <= m; i++) {
		memset(vis, 0, sizeof(vis));
		ans = 0;
		cin >> xx >> yy;
		dfs(xx, yy);
		cout << ans << endl;
	}
	return 0;
}