AOJ 0535 Crossing Black Ice

こんにちは川です。

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

一度通ったところは０にして、一番深い位置に来たらreturn する前に

１に戻すみたいなことしています。

まだ解いていなかったのが悲しい。

ソースコード

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

    }

}