読者です 読者をやめる 読者になる 読者になる

AOJ0535 Crossing Black Ice

まあ深さ優先するだけ

簡単だけど一発で通って嬉しかった 10分

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int m, n, ans;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int ice[100][100];
bool vis[100][100]; 

bool in(int x, int y){ return x >= 0 && y >= 0 && x <= m && y <= n && ice[y][x] == 1 && !vis[x][y]; }

int dfs(int x, int y){
    int tmp = 0;
    vis[x][y] = true;
    for(int i = 0; i < 4; i++){
	int nx = x + dx[i], ny = y + dy[i];
	if(in(nx, ny)){
	    tmp = max(tmp, dfs(nx, ny));
	    vis[nx][ny] = false;
	}
    }
    return tmp + 1;
}

int main(){
    while(scanf("%d %d", &m, &n), m || n){
	ans = 0;
	memset(ice, 0, sizeof(ice));
	for(int i = 0; i < n; i++){
	    for(int j = 0; j < m; j++){
		scanf("%d", &ice[i][j]);
	    }
	}
	for(int i = 0; i < n; i++){
	    for(int j = 0; j < m; j++){
		if(ice[i][j] == 1){
		    memset(vis, 0, sizeof(vis));
		    ans = max(ans, dfs(j, i));
		}
	    }
	}
	printf("%d\n", ans);
    }
    return 0;
}