CF374C Inna and Dima 题解

题目链接：CF374C Inna and Dima

题意：

Inna和Dima在商店买了一张 n * m 的桌子，桌子的每一个单元格上都有一个字符，字符集为(“D”,”I”,”M”,”A”)。

Inna实在是太爱Dima了，所以她想在桌子上找出一条最长的路线，使得这条路线中包含尽可能多的Dima的名字（有序，即必须是连续的DIMA）。

Inna的路线选取方式会遵循以下原则：

1.一开始，Inna会在桌子上找到所有的”D”，把他们作为起点。

2.Inna会在当前格子的周围四个相邻的格子中选取一个格子，她会从”D”走到”I”，从”I”走到”M”，从”M”走到”A”。这样，她就认为自己走完了一次Dima的名字。

3.Inna每走完一个格子，就会在该格子四周相邻的四个格子中选一个走，即上下左右四个方向，（当然，她不能走出这张桌子）。Inna从不跳过一个字母。因此，从字母”D”开始，她总是走到字母”I”，从字母”I”开始，她总是走到字母”M”，从字母”M”开始，她总是走到字母”A”，从字母”A”开始，她总是走到字母”D”。

因为桌子的不同，Inna能走的Dima的名字的次数也不同，有时她可以走有限次，有时她可以走无限次，有时她甚至不能走完一次Dima的名字。

现在，她想知道她能否至少走完一次Dima的名字。若可以，她最多能走多少次或者她能否走无限次？

纯记忆化搜索

从每个D都跑一下

对于无限的情况，

只要判断下一个可行格子是不是已经visited了

注意记忆化搜索使用dis数组更新答案

不是靠每次dfs的step

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)
int n,m,ans;
char a[N][N];
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int vis[N][N],dis[N][N];
bool safe(int x,int y)
{return 1<=x&&x<=n&&1<=y&&y<=m;}
void dfs(int x,int y)
{
    if(dis[x][y])return;
    vis[x][y]=1;
    dis[x][y]=1;
    for(int k=0; k<4; k++)
    {
        int tx=x+dx[k];
        int ty=y+dy[k];
        if(!safe(tx,ty))continue;
        if(!(a[x][y]=='D'&&a[tx][ty]=='I'||
           a[x][y]=='I'&&a[tx][ty]=='M'||
           a[x][y]=='M'&&a[tx][ty]=='A'||
           a[x][y]=='A'&&a[tx][ty]=='D'))continue;
        if(vis[tx][ty]){cout << "Poor Inna!";exit(0);}
        dfs(tx,ty);
        dis[x][y]=max(dis[x][y],dis[tx][ty]+1);
    }
    vis[x][y]=0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> a[i]+1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(a[i][j]=='D'&&!vis[i][j])
            dfs(i,j),ans=max(ans,dis[i][j]);
        }
    ans/=4;
    if(ans==0)cout << "Poor Dima!";
    else cout << ans;
    return 0;
}