D. Explorer Space(dfs+剪枝)

Problem - 1517D - Codeforces 

题目大意：给你一个n行m列的矩阵，以及每个点上下左右相邻点的边权，求出每个点任意走k步后再回到当前这个点的最小路程，如果不能回到起始点则输出-1

思路：既然走k步后要回到起始点，则k一定要为偶数，若为奇数则每个点输出-1，否则我们只需要求从起始点走k/2步的最小路程，注意这里不能使用Dijkstra,因为可以重复走某些点，Dijkstra走过的点如果不进行标记容易超时，所以我们考虑使用dfs+记忆化，设置一个记忆化数组dp[i][j][c]表示（i，j)这个位置再走c步的最小路程。

Code:

int n,m,k;
map<PII,int> mp;
int dp[505][505][25];
int ne[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int dfs(int x,int y,int c)
{
  if(c==0) return dp[x][y][c]=0;
  if(dp[x][y][c]) return dp[x][y][c];
  int mn=1e18;
  for(int i=0;i<4;i++)
  {
    int tx=x+ne[i][0],ty=y+ne[i][1];
    if(tx>=1&&tx<=n&&ty>=1&&ty<=m)
    {
      mn=min(mn,dfs(tx,ty,c-1)+mp[{(x-1)*m+y,(tx-1)*m+ty}]);
    }
  }

  return dp[x][y][c]=mn;
}
void solve()
{
   cin>>n>>m>>k;

   for(int i=1;i<=n;i++)
   {
     for(int j=1;j<m;j++)
     {
      int x;cin>>x;
      int a=(i-1)*m+j;
      int b=a+1;
      mp[{a,b}]=mp[{b,a}]=x; 
     }

   }

   for(int i=1;i<n;i++)
   {
    for(int j=1;j<=m;j++)
    {
      int x;cin>>x;
      int a=(i-1)*m+j;
      int b=a+m;
      mp[{a,b}]=mp[{b,a}]=x;
    }
   }
   if(k&1)
   {
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++) cout<<-1<<' ';
        cout<<endl;
    }
    return ;
   }
   k/=2;
   for(int i=1;i<=n;i++)
   {
    for(int j=1;j<=m;j++)
    {
      cout<<dfs(i,j,k)*2<<' ';
    }
    cout<<endl;
   }
}