0分RE,思路样例感觉都没问题
查看原帖
0分RE,思路样例感觉都没问题
795542
LoveYuigahamaYui楼主2024/7/10 15:51

大佬求调

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010;
int n, m;
int c[N][N];
int h[N][N];
int ans[100010];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int bfs(int sx, int sy, int k)
{
	int sum = 1;
	queue<PII> q;
	q.push({sx, sy});
	h[sx][sy] = k;
	while (q.size())
	{
		PII t = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i)
		{
			int x = t.first + dx[i];
			int y = t.second + dy[i];
			if (x >= 1 && x <= n && y >= 1 && y <= n && c[x][y] + c[t.first][t.second] == 1 && !h[x][y])
			{
//				if (ans[x][y]) return ans[x][y];
				sum++;
				h[x][y] = k;
				q.push({x, y});
			}
		}
	}
	ans[k] = sum;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			char s;
			cin >> s;
			if (s == '0') c[i][j] = 0;
			else c[i][j] = 1;
		}
	}
	for (int i = 1; i <= m; ++i) 
	{
		int x, y;
		cin >> x >> y;
		if (h[x][y])
		{
			cout << ans[h[x][y]] << endl;
		}
		else
		{
			bfs(x, y, i);
			cout << ans[i] << endl;	
		}
	}
}
2024/7/10 15:51
加载中...