How Many Island?
#include <stdio.h> int filledp(int map[][50],int w, int h) { int i,j; int filledp = 1; for(i = 0; i < h; i++) { for(j = 0; j < w; j++) { if(map[i][j] == 1) { filledp = 0; } } } return filledp; } void mark(int map[][50], int x, int y, int w, int h, int flag) { if(filledp(map,w,h)) return; if((x < 0) || (x >= w) || (y < 0) || (y >= h)) return; if(map[y][x] == 0) return; if(map[y][x] == 1) { map[y][x] = flag; mark(map, x-1,y-1,w,h,flag); mark(map, x-1,y,w,h,flag); mark(map, x-1,y+1,w,h,flag); mark(map, x,y-1,w,h,flag); mark(map, x,y+1,w,h,flag); mark(map, x+1,y-1,w,h,flag); mark(map, x+1,y,w,h,flag); mark(map, x+1,y+1,w,h,flag); } return; } int countIsland(int map[][50],int w, int h,int cnt) { if(filledp(map,w,h)) return cnt; int i,j; for(i = 0; i < h; i++) { for(j = 0; j < w; j++) { //Find no marked cell if(map[i][j] == 1) { mark(map,j,i,w,h,cnt+2); return countIsland(map,w,h,cnt+1); } } } } void printMap(int map[][50], int w, int h) { int i,j; for(i = 0; i < h; i++) { for(j = 0; j < w; j++) { printf("%d",map[i][j]); } printf("\n"); } } int main() { int w,h; while(1) { scanf("%d %d",&w,&h); if(w == 0 && h == 0) break; int map[h][50]; int i,j; for(i = 0; i < h; i++) { for(j = 0; j < w; j++) { scanf(" %d",&map[i][j]); } } printf("%d\n",countIsland(map,w,h,0)); } }
再帰的で破壊的にCで。