Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/416-aaf04de4
この記事にトラックバックする(FC2ブログユーザー)

Aizu 1160 - How Many Islands? (島はいくつある?) (この記事を編集する[管理者用])

Source
ACM/ICPC Japan Domestic 2009
Aizu 1160

問題概要
日本語なので略.

解法
塗りつぶしながら数える.DFS.

C言語によるスパゲッティなコード
#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int mp[60][60],x,y;

void sol(int i,int j){
  int ii,jj;
  if(i<0||j<0||i>=x||j>=y) return;
  if(mp[i][j]==0) return;
  mp[i][j]=0;
  REP(ii,-1,2) REP(jj,-1,2) sol(i+ii,j+jj);
}

int main(){
  int i,j,res;

  for(;;){
    scanf("%d%d",&y,&x); if(!x)break; res=0;
    rep(i,x) rep(j,y) scanf("%d",mp[i]+j);
    rep(i,x) rep(j,y) if(mp[i][j]) res++, sol(i,j);
    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/416-aaf04de4
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。