时间复杂度爆炸,3TLE,7AC
  • 板块P1141 01迷宫
  • 楼主jifei
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/11/17 08:29
  • 上次更新2023/11/4 00:21:24
查看原帖
时间复杂度爆炸,3TLE,7AC
316494
jifei楼主2021/11/17 08:29

不想大改了,还能再优化抢救一下吗QAQ

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt;
char mapp[1005][1005];
bool mark[1005][1005];
int move_x[4] = {0, 0, 1, -1};
int move_y[4] = {1, -1, 0, 0};
void ReSet() {
	cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			mark[i][j] = false;
		}
	}
}
void bfs(int x, int y) {
	mark[x][y] = true;
	cnt++;
	for (int i = 0; i < 4; i++) {
		int xx = x + move_x[i], yy = y + move_y[i];
		if (xx >= 0 && yy >= 0 && xx < n && yy < n && mapp[xx][yy] != mapp[x][y] && !mark[xx][yy]) {
			bfs(xx, yy);
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mapp[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		ReSet();
		int x, y;
		cin >> x >> y;
		bfs(x - 1, y - 1);
		cout << cnt << endl;
	}
	return 0;
}
2021/11/17 08:29
加载中...