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;
}