能帮忙看下我的DFS哪里有问题吗?

回复帖子

@幽灵特工 2020-09-15 18:21 回复
#include <bits/stdc++.h>
using namespace std;
int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int ans=0;
int a1,a2,a3,a4;
int maps[5][9]={0};
struct point{
    int x;
    int y;
}n,now,next;
int visit[5][9]={0};
void DFS(point a){
    now.x=a.x;
    now.y=a.y;
    if(now.x==a1&&now.y==a2){
        ans++;
        return;
    }
    visit[a.x][a.y]=1;
    for(int i=0;i<4;i++){
        for(int j=0;j<2;j++){
            if(maps[now.x+move[i][j]][now.y+move[i][j]]==0&&visit[now.x+move[i][j]][now.y+move[i][j]]==0
                &&now.x+move[i][j]>=0&&now.x+move[i][j]<=4&&now.y+move[i][j]>=0&&now.y+move[i][j]<=9){
                next.x=now.x+move[i][j];
                next.y=now.y+move[i][j];
                DFS(next);
            }
        }
    }
}
queue <point> q;

int main(){
    cin>>a1>>a2>>a3>>a4;
    n.x=0;
    n.y=0;//起始位置 
    maps[a3][a4]=1;
    maps[a3-2][a4+1]=1;
    maps[a3-2][a4-1]=1;
    maps[a3-1][a4+2]=1;
    maps[a3-1][a4-2]=1;
    maps[a3+2][a4+1]=1;
    maps[a3+2][a4-1]=1;
    maps[a3+1][a4+2]=1;
    maps[a3+1][a4-2]=1;
    //记录不能走的坐标 
    DFS(n);
    cout<<ans;
}
@metaphysis 2020-09-15 19:26 回复 举报

@幽灵特工

如果您一定要用DFS,那么应该逆着推,即采用“自顶向下”的递推方法,同时使用“记忆化”技巧,这实际上是DP的一种形式。常规的是使用“自底向上”式的递推,即两层循环的迭代来控制DP过程。

使用“自顶向下”式递归求解并结合记忆化技巧的参考代码:

#include <bits/stdc++.h>

using namespace std;

long long dp[32][32];

long long dfs(int x, int y)
{
    if (x < 0 || y < 0) return 0;
    if (~dp[x][y]) return dp[x][y];
    return dp[x][y] = dfs(x - 1, y) + dfs(x, y - 1);
}

int main(int argc, char *argv[])
{
    int tx, ty, kx, ky;
    cin >> tx >> ty >> kx >> ky;
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 1;
    for (int i = -2; i <= 2; i++)
        for (int j = -2; j <= 2; j++)
            if (i * i + j * j == 5 && (kx + i) >= 0 && (ky + j) >= 0)
                dp[kx + i][ky + j] = 0;
    dp[kx][ky] = 0;
    cout << dfs(tx, ty) << '\n';
    return 0;
}
@幽灵特工 2020-09-16 12:47 回复 举报

@metaphysis 我这样写有什么问题吗?

#include <bits/stdc++.h>
using namespace std;
long long dp[21][21]={0};
long long visit[21][21]={0};
int a,b,c,d;
long long sol(int dx,int dy){
    if(dx<0||dy<0)return 0;
    if(visit[dx][dy])return dp[dx][dy];
    dp[dx][dy]=sol(dx-1,dy)+sol(dx,dy-1);
    visit[dx][dy]=1;
    return dp[dx][dy];
}

int main(){
    dp[0][0]=1;
    cin>>a>>b>>c>>d;
    for(int i=-2;i<=2;i++){
        for(int j=-2;j<=2;j++){
            if(i*i+j*j==5){
                dp[c+i][d+j]=0;
            }
        }
    } 
    dp[c][d]=0;
    cout<<sol(a,b);
}
@metaphysis 2020-09-16 14:23 回复 举报

@幽灵特工

#include <bits/stdc++.h>
using namespace std;
// 数组范围要大一些,要不然会导致越界。
long long dp[32][32]={0};
long long visit[32][32]={0};
int a,b,c,d;
long long sol(int dx,int dy){
    if(dx<0||dy<0)return 0;
    if(visit[dx][dy]) return dp[dx][dy];
    dp[dx][dy]=sol(dx-1,dy)+sol(dx,dy-1);
    visit[dx][dy]=1;
    return dp[dx][dy];
}

int main(){
    // 标记起点已经计算。
    visit[0][0] = 1;
    dp[0][0]=1;
    cin>>a>>b>>c>>d;
    for(int i=-2;i<=2;i++){
        for(int j=-2;j<=2;j++){
            // 注意不要忘了范围检查,网格类的题目,这是常规操作。
            if(i*i+j*j==5 && c + i >= 0 && d + j >= 0){
                dp[c+i][d+j]=0;
                // 标记马能控制的点为已经访问,表示一遇到此点即可返回。
                visit[c + i][d + j] = 1;
            }
        }
    } 
    dp[c][d]=0;
    // 标记马本身的位置为已经访问。
    visit[c][d] = 1;
    cout<<sol(a,b);
}

有空请您访问我的 CSDN博客,里面有我写的一本书,内有编程竞赛相关内容的介绍,并附有对应的练习题目(题目源自UVa OJ),可免费下载此书的PDF版本:《C++,挑战编程——程序设计竞赛进阶训练指南》

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。