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

川のブログ

川の適当気ままなブログです。 

AOJ 0535 Crossing Black Ice

AOJ volume5

こんにちは川です。

今回は、深さ優先探索ですね。

一度通ったところは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;
    }
}