题目大意是有一个DIMA四种字母组成的矩阵，要在矩阵中找最长的DIMADIMADIMA……串，连接方式为四方向连接，问最长能找到多少DIMA。字母可以重复访问，如果DIMA串成环，即可以取出无限长的DIMA串，则输出特定字符串，若没有DIMA串，也输出另一特定字符串，否则输出最长多少DIMA串。
这是我大一暑假的时候做的，并且当时WA在第23组上，后来就没继续做这个题了，现在不想看大一的代码了。
重新想了一下，其实就是判图中是否有环，无环的话，DIMA的链最长多少，也就是找图中以D字母开头的最长链。
那么读入之后对D->I I->M M->A A->D 进行建边，并判环以及求最长链即可。
我考虑判环和求最长链长度都可以通过DFS实现，所以就只写了一个DFS函数。
DFS当然是没有写错的，但是发现在第10组T了。想了一下，DFS总复杂度是O(n^2+m)的，m为边数，因为所有点和边都只会被DFS一次，我全部从D字母开始搜索。此时因为我判环有提前return的操作，会导致vis没有清空，因此我在每次DFS前有memset掉vis数组的操作。如果D特别多，则memset每次都是O(n^2)的复杂度，就会超时。我修改了一下，将DFS过程中的return前都将vis置为0，就不用memset了，于是就过了。
其实如果将判环和求最长链分开，或许就不会出现这样的问题，比如用拓扑序判环，肯定不会出现大量memset。判完环再求最长链，则已经知道图中没有环，DFS每个点必定只需要访问一次，就不需要memset了。
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
typedef long long ll;
const int mod = 1e9 + ;
const int INF = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = 1e6 + ; int n,m;
int xx[] = {,-,,};
int yy[] = {,,,-};
char s[][];
int id[][];
int dis[maxn];
int head[maxn],point[maxn<<],nxt[maxn<<],size;
int vis[maxn];
bool flag = false; void init(){
size = ;
memset(head,-,sizeof(head));
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
flag = false;
} void add(int a, int b){
point[size] = b;
nxt[size] = head[a];
head[a] = size++;
} void dfs(int s){
if(dis[s])return;
vis[s] = ;
dis[s] = ;
for(int i = head[s] ; ~ i ; i = nxt[i]){
int j = point[i];
if(vis[j]){flag = true;vis[s] = ;return;}
dfs(j);
if(flag){vis[s] = ;return;}
dis[s] = max(dis[s],dis[j]+);
}
vis[s] = ;
} int main(){
scanf("%d%d",&n,&m);
for(int i = ; i <= n ; ++ i)scanf("%s",s[i]+);
int cnt = ;
for(int i = ; i <= n ; ++ i){
for(int j = ; j <= m ; ++ j){
id[i][j] = ++ cnt;
}
}
init();
for(int i = ; i <= n ; ++ i){
for(int j = ; j <= m ; ++ j){
for(int k = ; k < ; ++ k){
int dx = i + xx[k];
int dy = j + yy[k];
if(dx < || dx > n || dy < || dy > m)continue;
if(s[i][j] == 'D' && s[dx][dy] == 'I')add(id[i][j],id[dx][dy]);
if(s[i][j] == 'I' && s[dx][dy] == 'M')add(id[i][j],id[dx][dy]);
if(s[i][j] == 'M' && s[dx][dy] == 'A')add(id[i][j],id[dx][dy]);
if(s[i][j] == 'A' && s[dx][dy] == 'D')add(id[i][j],id[dx][dy]);
}
}
}
int ans = ;
for(int i = ; i <= n ; ++ i){
for(int j = ; j <= m ; ++ j){
if(s[i][j] != 'D')continue;
dfs(id[i][j]);
if(flag == true){
printf("Poor Inna!\n");
return ;
}
if(dis[id[i][j]] > ans)ans = dis[id[i][j]];
}
}
ans /= ;
if(ans)printf("%d\n",ans);
else printf("Poor Dima!\n");
return ;
}