Codeforces 374C - Inna and Dima

374C - Inna and Dima

思路：dfs+记忆化搜索

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll unsigned long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int INF=0x3f3f3f3f;

char mp[][];

bool vis[][];

int  dp[][];

int dir[][]={,,,,,-,-,};

int n,m;

int dfs(int x,int y){

    if(dp[x][y]!=-)return dp[x][y];

    dp[x][y]=;//当前路径染色，方便判环

    int ans=;

    bool f=false;

    for(int i=;i<;i++){

        int tx=x+dir[i][];

        int ty=y+dir[i][];

        if(x<||x>n||y<||y>m)continue;

        if(mp[x][y]=='D'&&mp[tx][ty]=='I'){

            if(dp[tx][ty]==)return INF;

            ans=max(ans,+dfs(tx,ty));

            f=true;

        }

        if(mp[x][y]=='I'&&mp[tx][ty]=='M'){

            if(dp[tx][ty]==)return INF;

            ans=max(ans,+dfs(tx,ty));

            f=true;

        }

        if(mp[x][y]=='M'&&mp[tx][ty]=='A'){

            if(dp[tx][ty]==)return INF;

            ans=max(ans,+dfs(tx,ty));

            f=true;

        }

        if(mp[x][y]=='A'&&mp[tx][ty]=='D'){

            if(dp[tx][ty]==)return INF;

            ans=max(ans,+dfs(tx,ty));

            f=true;

        }

    }

    if(!f)return dp[x][y]=;

    else return dp[x][y]=ans;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie();

    cin>>n>>m;

    for(int i=;i<=n;i++){

        cin>>(mp[i]+);

    }

    mem(dp,-);

    int ANS=;

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            if(mp[i][j]=='D'){

                ANS=max(ANS,dfs(i,j));

            }

        }

    }

    //cout<<ANS<<endl;

    if(ANS>=INF)cout<<"Poor Inna!"<<endl;

    else{

        if(ANS/==)cout<<"Poor Dima!"<<endl;

        else cout<<ANS/<<endl;

    }

    return ;

}