洛谷p1141-01迷宫
作者:
踢足球的程序员
,
2024-03-28 20:34:45
,
所有人可见
,
阅读 5
date : 2024/3/28
time : 20:33
algorithm : bfs + 连通块优化
//连通块优化思想
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1005, M = 1e6 + 10;
int n, m;
char g[N][N];
int blocknum[M];//连通块数目
int blocks[N][N];//连通块编号
int block;
int bfs(int x1, int y1)
{
queue<PII> q;
int res = 1;
q.push({x1, y1});
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while(q.size())
{
auto t = q.front();
q.pop();
int a1 = t.first, b1 = t.second;
for(int j = 0; j < 4; j ++)
{
int a = a1 + dx[j], b = b1 + dy[j];
if(a >= 1 && a <= n && b >= 1 && b <= n && g[a][b] ^ g[a1][b1] && !blocks[a][b])
{
blocks[a][b] = block;
blocknum[block] ++;
q.push({a, b});
}
}
}
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++ )
{
cin >> g[i][j];
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
if(!blocks[i][j])
{
block ++;
blocks[i][j] = block;
blocknum[block] ++;
bfs(i, j);
}
}
int qa, qb;
for(int i = 1; i <= m; i ++)
{
cin >> qa >> qb;
cout << blocknum[blocks[qa][qb]] << endl;
}
return 0;
}