AOJ 0535: Crossing Black Ice
DFS(深さ優先探索)の典型問題。m+2 × n+2のマップを使うとマップ外に出なくなるのでオススメです。
#include<cstdio> #include<algorithm> using namespace std; int m,n,unused[90][90],dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; int dfs(int y, int x, int d){//座標と、今までに割った氷の枚数 int res = d; for(int i = 0; i < 4; i++){ int ty = y+dy[i],tx = x+dx[i]; if(ty>=0&&tx>=0&&ty<n&&tx<m&&unused[ty][tx]){//一回り大きいマップを使うと一番右だけで良い unused[ty][tx] = 0; res = max(res,dfs(ty,tx,d+1)); unused[ty][tx] = 1; } } return res; } int main(){ while(scanf("%d%d",&m,&n),m){ int res = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ scanf("%d",unused[i]+j); } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(unused[i][j]){ unused[i][j] = 0; res = max(res,dfs(i,j,1)); unused[i][j] = 1; } } } printf("%d\n",res); } return 0; }