#include #include #include #include int wormAmountCalculator(std::vector>&, int, int); void dfs(std::vector>&, std::vector&, int, std::vector&); int main(int argc, char* argv[]){ int T; scanf("%d", &T); for(int i = 0; i < T; i++){ int M, N, K; scanf("%d %d %d", &M, &N, &K); std::vector> ground(N, std::vector(M, false)); for(int j = 0; j < K; j++){ int x, y; scanf("%d %d", &x, &y); ground[y][x] = true; } printf("%d\n", wormAmountCalculator(ground, M, N)); } } int wormAmountCalculator(std::vector>& ground, int M, int N){ std::vector> graph(N*M); for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ if(ground[i][j]){ if(i-1 >= 0 && ground[i-1][j]){ graph[i*M + j].emplace_back((i-1)*M + j); } if(i+1 < N && ground[i+1][j]){ graph[i*M + j].emplace_back((i+1)*M + j); } if(j-1 >= 0 && ground[i][j-1]){ graph[i*M + j].emplace_back(i*M + j-1); } if(j+1 < M && ground[i][j+1]){ graph[i*M + j].emplace_back(i*M + j+1); } } } } std::map findList; for(int i = 0; i < N*M; i++){ findList[i] = true; } int wormCount = 0; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ if(findList[i*M + j] && ground[i][j]){ std::vector result; std::vector visited(graph.size() + 1, false); dfs(graph, visited, i*M + j, result); wormCount++; for(int i : result){ findList[i] = false; } } } } return wormCount; } void dfs(std::vector>& graph, std::vector& visited, int R, std::vector& result){ visited[R] = true; result.emplace_back(R); for(int V : graph[R]){ if(!visited[V]){ dfs(graph, visited, V, result); } } }

코드 #1322