PKU 1856 Sea Battle
http://poj.org/problem?id=1856
長方形のボードが与えられるので、そのボードにコーナでも接していない長方形がいくつあるかを数えろというような問題。
そのようなもの以外があればそれを検出しなければならない。
dfsしました。
入力のサイズがでかいですが、O(1000*1000)程度に収まっているはずです。
int n,m; int rx,lx,hy,ly; char in[1002][1002]; int dfs(int x,int y){ int ret=1; rx=min(rx,x); lx=max(lx,x); hy=min(hy,y); ly=max(ly,y); in[x][y]=0; rep(i,8){ int nx=x+dx[i],ny=y+dy[i]; if(in[nx][ny]!='#')continue; ret+=dfs(nx,ny); } return ret; } void solve(){ rep(i,n)scanf("%s",in[i+1]+1); memset(in[n+1],0,sizeof(in[n+1])); n+=2; m+=2; int ans=0; rep(i,n)rep(j,m){ if(in[i][j]!='#')continue; ++ans; rx=i,lx=i,hy=j,ly=j; int visnum=dfs(i,j); if(visnum!=(lx-rx+1)*(ly-hy+1)){ cout<<"Bad placement."<<endl; return; } } cout<<"There are "<<ans<<" ships."<<endl; } main(){ while(cin>>n>>m,n)solve(); }