http://codeforces.com/contest/374/problem/C
记忆化搜索，题意：求按照要求可以记过名字多少次，如果次数为无穷大，输出Poor Inna!，如果不经过一次输出Poor Dima!，否则输出输出次数。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1001
#define LL __int64
using namespace std;
const LL inf=; int n,m;
char g[maxn][maxn];
LL dp[maxn][maxn];
int dir[][]={{,},{-,},{,},{,-}};
LL max1(LL a,LL b)
{
return a>b?a:b;
}
LL min1(LL a,LL b)
{
return a>b?b:a;
} LL dfs(int x,int y)
{
if(dp[x][y]!=-) return dp[x][y];
dp[x][y]=inf;
int c=;
for(int i=; i<; i++)
{
int xx=x+dir[i][];
int yy=y+dir[i][];
if(xx>=&&xx<n&&yy>=&&yy<m)
{
if((g[x][y]=='D'&&g[xx][yy]=='I')||(g[x][y]=='I'&&g[xx][yy]=='M')||(g[x][y]=='M'&&g[xx][yy]=='A')||(g[x][y]=='A'&&g[xx][yy]=='D'))
{
c=max1(c,dfs(xx,yy));
}
}
}
return dp[x][y]=min1(inf,c+);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,-,sizeof(dp));
for(int i=; i<n; i++)
{
scanf("%s",g[i]);
}
LL ans=;
for(int i=; i<n; i++)
{
for(int j=; j<m; j++)
{
if(g[i][j]=='D')
{
ans=max1(ans,dfs(i,j));
}
}
}
if(ans==inf)
{
printf("Poor Inna!\n");
}
else
{
LL y=ans/;
if(y==)
{
printf("Poor Dima!\n");
}
else
printf("%I64d\n",y);
}
}
return ;
}