当前位置：Gxlcms > html代码 > CodeforcesRound#220(Div.2)C题：InnaandDima（记忆化搜索+DP）_html/css_WEB-ITnose

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

时间：2021-07-01 10:21:17 帮助过：33人阅读

题目地址：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=0&&b=INF)    {        puts("Poor Inna!");    }    else        printf("%d\n",max1/4);    return 0;}

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

人气教程排行