AOJ 0535 Crossing Black Ice
こんにちは川です。
今回は、深さ優先探索ですね。
一度通ったところは0にして、一番深い位置に来たらreturn する前に
1に戻すみたいなことしています。
まだ解いていなかったのが悲しい。
#include <bits/stdc++.h>
using
namespace
std;
bool
ice[90][90];
int
n,m;
int
di[]={0,-1,0,1},dj[]={1,0,-1,0};
int
serch(
int
now,
int
i,
int
j)
{
int
ans=0;
ice[i][j]=0;
for
(
int
k=0;k<4;k++)
if
(i+di[k]>-1&&i+di[k]<m&&j+dj[k]>-1&&
j+dj[k]<n&&ice[i+di[k]][j+dj[k]])
ans=max(ans,serch(now+1,i+di[k],j+dj[k]));
ice[i][j]=1;
return
max(ans,now);
}
int
main() {
while
(cin>>n>>m,n,m){
for
(
int
i=0;i<m;i++){
for
(
int
j=0;j<n;j++)cin>>ice[i][j];
}
int
ans=0;
for
(
int
i=0;i<m;i++){
for
(
int
j=0;j<n;j++){
if
(ice[i][j]==1)ans=max(ans,serch(1,i,j));
}
}
cout<<ans<<endl;
}
}