#include
#include
using namespace std;
const int MAX = 51;
int n, m, k;
int lettuce[MAX][MAX];
int indexs;
int visited[MAX][MAX];
struct Move {
int x, y;
};
Move mv[4] = { {-1,0}, {1,0}, {0,1}, {0,-1} };
void dfs(int i, int j) {
for (int k = 0; k < 4; k++) {
int movei = i + mv[k].x;
int movej = j + mv[k].y;
if (movei >= 0 && movei < m && movej >= 0 && movej < n && lettuce[movei][movej] && visited[movei][movej]== 0) {
visited[movei][movej] = 1;
lettuce[movei][movej] = indexs;
dfs(movei, movej);
}
}
}
int main(void) {
int testcase;
cin >> testcase;
for (int t = 0; t < testcase; t++) {
cin >> n >> m >> k;
memset(lettuce, 0, sizeof(lettuce));
memset(visited, 0, sizeof(visited));
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
lettuce[y][x] = 1;
}
indexs = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (lettuce[i][j] == 1) {
indexs++;
visited[i][j] = 1;
dfs(i, j);
}
}
}
cout << indexs-1 << endl;
}
return 0;
}
'백준 알고리즘 > BFS' 카테고리의 다른 글
백준 2468번 C++ (0) | 2019.08.10 |
---|---|
백준 11403번 C++ (0) | 2019.08.08 |
백준 7576번 C++ (0) | 2019.08.08 |
백준 2667번 C++ (0) | 2019.08.08 |
백준 1697번 C++ (0) | 2019.08.07 |