/* 1611 유기농 배추 1654 40 1012 번문제입니다. 배추를 흰지렁이의 마리 수를 출력하세요. 섬의 갯수를 세는 문제와 동일 합니다. 1이 있는 곳에서 갈 수 있는 곳에 비지트 처리를 하고, 또 다른 1을 찾아서 비지트 처리를 하고 이런식으로 하면서 cnt++ 를 visit 에 넣으면 됩니다. 오께이. */ #include <iostream> #include <queue> #include <memory.h> using namespace std; #define SIZE 51 // 50; int W, H; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int ans; int a, b; int x, y, nx, ny; int dx[] = { 0,0,1,-1,-1,-1,1,1 }; int dy[] = { 1,-1,0,0,-1,1,-1,1 }; int wormCnt = 1; struct points { int x, y; }; queue<points> que; void problemIn() { for (int i = 0; i <H; i++) { for (int j = 0; j < W; j++) { cin >> map[i][j]; } } } void init() { wormCnt = 1; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { map[i][j] = 0; visit[i][j] = 0; } } } void bfs() { while (!que.empty()) { x = que.front().x; y = que.front().y; que.pop(); for (int i = 0; i < 8; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < H && ny < W && visit[nx][ny] == 0 && map[nx][ny] == 1) { visit[nx][ny] = wormCnt; que.push({ nx,ny }); } } }
} void solve() { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (map[i][j] == 1 && visit[i][j] == 0) { que.push({ i,j }); visit[i][j] = wormCnt; bfs(); wormCnt++; } } } } int main() { while (1) { cin >> W >> H; if (W == 0 && H == 0) break; problemIn(); solve(); cout << wormCnt - 1 << endl; init(); } return 0; }
|
와우, 가로 세로에 대해서, 문제 다르면 그냥 새로 짜주는게 디버깅에도 좋음 아니면 처음에 어디를 바꾸어 주어야 하는지 명확하게 명시하고 시작하는 것도 좋습니다. 이제 문제를 이해하면 모든지 짤 수 있습니다. |