首页 / HTML / CodeforcesRound#220(Div.2)C题：InnaandDima（记忆化搜索+DP）_html/css_WEB-ITnose

CodeforcesRound#220(Div.2)C题：InnaandDima（记忆化搜索+DP）_html/css_WEB-ITnose

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#220(Div.2)C题：InnaandDima（记忆化搜索+DP）_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1275字，纯文字阅读大概需要2分钟。

内容图文

题目地址：http://codeforces.com/problemset/problem/374/C

用dp[i][j]代表第i行第j列的数可以走的最大距离。为-1时表示未走过，将走过但未走完的暂时标记为INF。这样假如有环的时候就返回INF了。然后用dfs搜。

代码如下：

#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL __int64const int INF=0x3f3f3f3f;char mp[1001][1001], str[]="DIMA";int dp[1001][1001];int jx[]={0,0,1,-1};int jy[]={1,-1,0,0};int n, m;int dfs(int x, int y, int tmp){    if(dp[x][y]!=-1) return dp[x][y];    dp[x][y]=INF;    int i, a, b, t=0;    tmp=(1+tmp)%4;    for(i=0;i<4;i++)    {        a=x+jx[i];        b=y+jy[i];        if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]==str[tmp])        {            t=max(t,dfs(a,b,tmp));        }    }    dp[x][y]=++t;    return t;}int main(){    int i, j, max1=0;    scanf("%d%d",&n,&m);    for(i=0;i<n;i++)    {        scanf("%s",mp[i]);    }    memset(dp,-1,sizeof(dp));    for(i=0;i<n;i++)    {        for(j=0;j<m;j++)        {            if(mp[i][j]=='D')            {                max1=max(max1,dfs(i,j,0));            }        }    }    if(max1/4==0)    {        puts("Poor Dima!");    }    else if(max1>=INF)    {        puts("Poor Inna!");    }    else        printf("%d\n",max1/4);    return 0;}

内容总结

以上是互联网集市为您收集整理的CodeforcesRound#220(Div.2)C题：InnaandDima（记忆化搜索+DP）_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#220(Div.2)C题：InnaandDima（记忆化搜索+DP）_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/399041.html

来源：【匿名】