競プロ今日の備忘録

問題を解いた上での気づき、反省を

AOJ_0118: Property Distribution

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118

蟻本の深さ優先探索の練習問題として取り組んだ。

今日は解くのに二時間かかった。

時間がかかった要因として、

・scanfでmapの読み込みがうまくいかなかった

 ⇒cinでstring的に読み込むことで改善

・cnt変数をグローバルにしてしまったせいで初期化ミス

 ⇒毎回初期化しなおした

・問題の読み込みが浅かった

 ⇒読んだ(それはそう)

などが挙げられる。

AOJ上に上がっていたほかの人のコードを読んで気づきを得られた。

本番ではこんなことできないので自分の中に蓄積しなければならない。

#include <bits/stdc++.h>

using namespace std;

int H,M,cnt=0;
char farm[100][100];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};


void dfs(int x, int y, char z){
 farm[x][y]='.';
 for(int i=0;i<4;i++){
 if(x+dx[i]>=0 && x+dx[i]<H && y+dy[i]>=0 && y+dy[i]<M && farm[x+dx[i]][y+dy[i]]==z) dfs(x+dx[i],y+dy[i],z);
 }
 return ;
}

int main(){
 while(1){
 scanf("%d %d",&H,&M);
 if(H==0 && M==0) break;

for(int i=0;i<H;i++){
 cin >> farm[i];
 }

 
 cnt=0;

for(int i=0;i<H;i++){
 for(int j=0;j<M;j++){
 if(farm[i][j]!='.'){
 cnt++; dfs(i,j,farm[i][j]);
 }
 }
 }


 printf("%d\n",cnt);
}
 return 0;
}