Codeforces Round #220 (Div. 2)C题：Inna and Dima（记忆化搜索+DP） - 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 __int64 const 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 ,max1/4); return 0; }