求调!!BFS TLE#1 #3 #10 #11
  • 板块P1141 01迷宫
  • 楼主MRQF_PHM
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/9 16:53
  • 上次更新2024/8/9 17:53:16
查看原帖
求调!!BFS TLE#1 #3 #10 #11
1056391
MRQF_PHM楼主2024/8/9 16:53

求调!! 感谢大佬!!

//2024-8-9 P1141 01迷宫 yishua by bong
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const int M = 1e5;
int n, m;
int a[N][N];
int ans;
string s;
int rx, ry;
bool flag[N][N];

struct node {
	int xx, yy;
};

void bfs(int x, int y) {
	queue<node>q;
	q.push({x, y});
	while (!q.empty()) {
		int x = q.front().xx;
		int y = q.front().yy;
		q.pop();
		if (x < 1 || x > n)
			continue;
		if (y < 1 || y > n)
			continue;
		if (flag[x][y] == 1)
			continue;
		//if (a[x][y] == a[rx][ry])
		//	continue;
		flag[x][y] = 1;
		ans++;
		//rx = x, ry = y;
		if (a[x][y] != a[x + 1][y])
			q.push({x + 1, y});
		if (a[x][y] != a[x - 1][y])
			q.push({x - 1, y});
		if (a[x][y] != a[x][y + 1])
			q.push({x, y + 1});
		if (a[x][y] != a[x][y - 1])
			q.push({x, y - 1});
	}
	cout << ans << '\n';
	memset(flag, 0, sizeof(flag));
	ans = 0;
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		for (int j = 0; j <= s.size() - 1; j++) {
			a[i][j + 1] = s[j];
		}
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		bfs(x, y);
	}
	return 0;
}
2024/8/9 16:53
加载中...