63 lines
1.5 KiB
C++
63 lines
1.5 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
int dx[] = {1, 0, -1, 0}; //r u l d
|
|
int dy[] = {0, -1, 0, 1}; //r u l d (u, d)
|
|
// ^ ^
|
|
vector<vector<int>> mp;
|
|
vector<int> parent;
|
|
vector<bool> visited;
|
|
int ans = 0;
|
|
int find(int x){
|
|
if(x != parent[x]) parent[x] = find(parent[x]);
|
|
return parent[x];
|
|
}
|
|
void merge(int x, int y){
|
|
int xa = find(x);
|
|
int ya = find(y);
|
|
if(xa != ya) parent[xa] = ya;
|
|
}
|
|
void dfs(int x, int y, int n, int num){
|
|
if(x < 0 || y < 0 || x >= n || y >= n) return;
|
|
visited[x * n + y] = true;
|
|
for(int i = 0; i < 4; i++){
|
|
int nx = x + dx[i];
|
|
int ny = y + dy[i];
|
|
if(nx >= 0 && ny >= 0 && ny < n && nx < n){
|
|
int numt = mp[nx][ny];
|
|
if(!visited[nx * n + y] && num != numt){
|
|
merge(nx * n + ny, x * n + y);
|
|
|
|
dfs(nx, ny, n, numt);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int main(){
|
|
int n, m;
|
|
cin >> n >> m;
|
|
mp.resize(n, vector<int>(n));
|
|
parent.resize(n * n);
|
|
visited.resize(n * n, false);
|
|
for(int i = 0; i < n; ++i){
|
|
for(int j = 0; j < n; ++j){
|
|
cin >> mp[i][j];
|
|
}
|
|
}
|
|
int a, b;
|
|
for(int i = 0; i < m; ++i){
|
|
cin >> a >> b;
|
|
a--; b--;
|
|
//一次
|
|
ans = 0;
|
|
/*for(int i = 0; i < n * n; ++i){
|
|
parent[i] = i;
|
|
}*/
|
|
visited.resize(n * n, false);
|
|
dfs(a, b, n, mp[a][b]);
|
|
cout << ans << endl;
|
|
}
|
|
return 0;
|
|
}
|