P7995 [USACO21DEC] Walking Home B题解

iiiiiiiiiiiiiiiiiii · 2021-12-25 10:51:49 · 题解

题目传送门

这道题的大意是要从地图的 (1, 1) 点起，走到 (n, n) 点，要求不能走在草堆上，并且转弯不能超过 k 次，求有多少种可行的方案。

很明显，这是一道搜索题。我们可以在 dfs 函数中定义四个参数：x，y，t，way ，分别表示当前的行、当前的列、当前转弯次数和方向（0 代表往右走，1 代表往下走）。代码如下：

//省略缺省源
int T,n,k,a[100][100];
int dfs(int x,int y,int t,int way)
{
    int sum=0;
    if(t>k||a[x][y])//如果转弯次数超过k次，或者该点是个草堆
        return 0;
    if(x==n&&y==n)//如果到达终点，方案数加一
        return 1;
    if(x<n&&!a[x+1][y])
        sum+=dfs(x+1,y,way?t:t+1,1);//往右走
    if(y<n&&!a[x][y+1])
        sum+=dfs(x,y+1,way?t+1:t,0);//往下走
    return sum;
}
int main()
{
    T=read();
    while(T--)
    {
        n=read(),k=read();
        char chr;
        for(int i=1;i<=n;i++)//输入地图
        {
            for(int j=1;j<=n;j++)
            {
                chr=getchar();
                if(chr=='.')
                    a[i][j]=0;
                else
                    a[i][j]=1;
            }
            chr=getchar();
        }
        printf("%d\n",dfs(1,2,0,0)+dfs(2,1,0,1));
    }
    return 0;
}

额，这就 90 分, TLE 了。

我们会发现：在 dfs 的求解过程中，有许多重复的子问题。

记忆化搜索能很好的解决这种问题：开一个四维数组，如果之前没有求解过该状态的，就把该状态的方案数记录下来。以后如果遇到同样的状态的话，就可以直接返回该状态的方案数了。这有点绕

并且，在开始的时候，我们要把整个记忆化数组初始化为 -1。代码如下：

//省略缺省源
int T,n,k,a[100][100],g[100][100][10][5];//记忆化数组
int dfs(int x,int y,int t,int way)
{
    int sum=0;
    if(t>k||a[x][y])
        return 0;
    if(g[x][y][t][way]!=-1)//如果该状态求解过
        return g[x][y][t][way];//直接返回该状态的方案数
    if(x==n&&y==n)
        return 1;
    if(x<n&&!a[x+1][y])
        sum+=dfs(x+1,y,way?t:t+1,1);
    if(y<n&&!a[x][y+1])
        sum+=dfs(x,y+1,way?t+1:t,0);
    g[x][y][t][way]=sum;//标记
    return sum;
}
//主函数见上