# 能帮忙看下我的ＤＦＳ哪里有问题吗？

@幽灵特工 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 回复 举报

@幽灵特工

#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);
}