Let's write β

プログラミング中にできたことか、思ったこととか

ICPC2009ProblemB

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で。