问题描述

传说，在蓝桥王国中一个极其神秘的森林。这个森林的起点在 (1,1)(1,1) ，终点在 (n,m)。在你进入这个森岭后，每次你只可以向下或者向右走，由于森岭的神秘力量，至多只可以改变 k 次方向。

小蓝现在想知道，一共有多少种方案可以从 (1,1)(1,1) 进入然后从 (n,m) 走出。数据保证至少存在一种方案。

输入格式

第 11 行包含三个正整数 n,m,k，分别表示地图的规模和可以改变方向的次数。

第 22 到 +1n+1 行包含 m 个字符，表示地图上该位置的信息，用.表示空地，#表示石头无法通行，保证起点和终点不为石头。

输出格式

输出共 11 行，包含 11 个整数，表示方案数。

我遇到的问题

这道题我知道是用dfs的方式来解，但是开始写程序的时候发现事情不对，第一，这题在递归调用的时候会出现大量的重复运算，所以需要进行记忆化搜索。第二，这道题的特别之处在于加入了一个改变方向的次数，说明还要记录他的方向状态，如果方向改变 k+1。当时想到这就不知道怎么写了

大佬的代码

//本题需要结合dfs+记忆化搜索+动态规划来解题
//对于当前坐标(i,j)，其下一步有两个转移方向，分别是向下(i+1,j)和向右(i,j+1)
//故从(i,j)到达(N,M)的方案数等于从(i+1,j)到(N,M)和从(i,j+1)到(N,M)的方案数之和
//由于最多转向K次，每次转移状态时需要记录当前方向和下一步转移的方向，以及已经转向的次数
//且每次回溯时都要恢复转向次数k，时间复杂度很高，因此使用记忆化数组保存中间结果 
//故使用四维记忆化数组进行记录，每转移一次都要传入当前坐标、当前方向、已转移次数等参量 
#include <bits/stdc++.h>

using namespace std;

char matrix[110][110];//迷宫矩阵 
int N,M,K;
int dp[105][105][2][7];//记忆化数组 
//dp[i][j][0][k]表示从(i,j)开始,方向向右，共改变了k次方向，能到达终点的方案数 
//dp[i][j][1][k]表示从(i,j)开始,方向向下，共改变了k次方向，能到达终点的方案数 
 
bool ok(int i,int j)//判断是否是可通行的点 
{
    if(i>N||j>M)return false;
    if(matrix[i][j]=='.')return true;
    else return false;    
} 

int dfs(int row,int col,int tag,int k)//从(row,col)开始进行dfs，当前方向为tag，总共改变了k次方向
{
    int cnt=0;//记录总方案数 
    if(!ok(row,col))return 0;//该点不可通行，直接返回0 
    if(row==N&&col==M)return 1;//到达终点，直接返回1，表示这是一种方案 
    if(dp[row][col][tag][k])return dp[row][col][tag][k];
    //已经搜索过该点，直接返回记忆化数组的值 


    if(k<K)//转向的次数没有超过K次 
    {
        cnt=cnt+dfs(row+1,col,1,tag==1?k:k+1);//向下 
        cnt=cnt+dfs(row,col+1,0,tag==0?k:k+1);//向右 
    }
    else if(k==K)//转向次数已经达到K次 
    {
        if(tag==0)//原来向右 
        {
            cnt=cnt+dfs(row,col+1,tag,k);//继续向右    
        } 
        else if(tag==1)//原来向下 
        {
            cnt=cnt+dfs(row+1,col,tag,k);//继续向下 
        }
    }
    dp[row][col][tag][k]=cnt;//记忆化，将从(row,col)到(N,M)的总方案数保存起来 
    return cnt;//返回从(row,col)到(N,M)的方案数 
}
 
int main()
{
    int ans=0;
    cin>>N>>M>>K;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            cin>>matrix[i][j];    
        }    
    }    
    
    //此处要注意一点，起点(1,1)处是没有当前方向的，需要前进一步才有方向 
    if(ok(1,2))ans=ans+dfs(1,2,0,0);//从(1,2)开始 
    if(ok(2,1))ans=ans+dfs(2,1,1,0);//从(2,1)开始 
    cout<<ans<<endl;
    return 0;
}

亮点的地方

定义了一个状态变量 tag 来表示当前的方向 ，tag==0表示向右，tag==1表示向下

if(k<K)//转向的次数没有超过K次 
    {
        cnt=cnt+dfs(row+1,col,1,tag==1?k:k+1);//向下 
        cnt=cnt+dfs(row,col+1,0,tag==0?k:k+1);//向右 
    }
    else if(k==K)//转向次数已经达到K次 
    {
        if(tag==0)//原来向右 
        {
            cnt=cnt+dfs(row,col+1,tag,k);//继续向右    
        } 
        else if(tag==1)//原来向下 
        {
            cnt=cnt+dfs(row+1,col,tag,k);//继续向下 
        }
    }
    dp[row][col][tag][k]=cnt;//记忆化，将从(row,col)到(N,M)的总方案数保存起来 
    return cnt;//返回从(row,col)到(N,M)的方案数 

用了一个三元条件运算符来判断方向是否改变，太强了！！