30求救!!!!!!!!!!!!!!
  • 板块P1141 01迷宫
  • 楼主Francium_
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/8/25 16:53
  • 上次更新2023/11/3 01:16:06
查看原帖
30求救!!!!!!!!!!!!!!
762086
Francium_楼主2023/8/25 16:53

结果\text {结果} 代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 102;
long long n, m;
long long fx, fy;

struct coordinate {
	long long x, y;
} ;
long long mmap[N][N], ans[N][N];
bool st[N][N];

void bfs() {
	memset(st, 0, sizeof(st));
	long long num = 0;
	queue<coordinate> q;
	coordinate nnew;
	nnew.x = fx, nnew.y = fy;
	q.push(nnew);
	while (!q.empty()) {
		coordinate now = q.front();
		q.pop();
		int x = now.x, y = now.y;
		if (x < 1 || x > n)
			continue;
		if (y < 1 || y > n)
			continue;
		if (st[x][y])
			continue;
		st[x][y] = true;
		num++;
		if (mmap[x][y]) {
			if (!mmap[x][y - 1]) {
				nnew.x = x;
				nnew.y = y - 1;
				q.push(nnew);
			}
			if (!mmap[x][y + 1]) {
				nnew.x = x;
				nnew.y = y + 1;
				q.push(nnew);
			}
			if (!mmap[x - 1][y]) {
				nnew.x = x - 1;
				nnew.y = y;
				q.push(nnew);
			}
			if (!mmap[x + 1][y]) {
				nnew.x = x + 1;
				nnew.y = y;
				q.push(nnew);
			}
		} else if (!mmap[x][y]) {
			if (mmap[x][y - 1]) {
				nnew.x = x;
				nnew.y = y - 1;
				q.push(nnew);
			}
			if (mmap[x][y + 1]) {
				nnew.x = x;
				nnew.y = y + 1;
				q.push(nnew);
			}
			if (mmap[x - 1][y]) {
				nnew.x = x - 1;
				nnew.y = y;
				q.push(nnew);
			}
			if (mmap[x + 1][y]) {
				nnew.x = x + 1;
				nnew.y = y;
				q.push(nnew);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (st[i][j]) {
				ans[i][j] = num;
			}
		}
	}
}

int main() {
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= n; j++) {
			mmap[i][j] = s[j - 1] - '0';
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!ans[i][j]) {
				fx = j;
				fy = i;
				bfs();
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		long long o, p;
		scanf("%lld%lld", &o, &p);
		printf("%lld\n", ans[o][p]);
	}
	return 0;
}
2023/8/25 16:53
加载中...