求大佬,很好奇为什么dfs不能做??还是我做错了?为什么一定要用dp
查看原帖
求大佬,很好奇为什么dfs不能做??还是我做错了?为什么一定要用dp
268893
马兔up楼主2023/2/16 18:02
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
 
using namespace std; 

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int n,m; //b的坐标 
 
int c,d; //马的坐标
 
int map [25][25];//地图 ,标记是否能走? 
int flag[25][25]; // 是否走过 

int t1[3] = {0,1,0};
int t2[3] = {0,1,1};
int t3[9] = {0,-1,-1,-2,-2,1,1,2,2};
int t4[9] = {0,-2,2,-1,1,-2,2,1,-1}; 

int ans = 0;

int cal(int c,int d)
{
	for(int i=1;i<=8;i++)
	map[c+t3[i]][d+t4[i]]=1;//不能走 
}

void dfs (int a,int b)
{
	if (a == n && b== m)
	{
		ans ++;
		return ;	
	} 
	else 
	{
		for (int i=1;i<=2;i++)
		{
			int z1=a+t1[i];
			int z2=b+t2[i];
			if(map[z1][z2]==0&&z1>=0&&z2>=0&&z1<=n&&z2<=m)//map为0表示可以走
			{
			 	//flag[z1][z2]=1; 
				dfs(z1,z2);
				//flag[z1][z2]=0;
			}
			
		}	
	}

}
/*
void pre()
{
	for(int i =0;i<25;i++)
	 {
		for(int j=0;j<25;j++)
	 	{
			map[i][j]=0; //可以走 
			flag[i][j]=0;	//没走过	
		}
	 }
}*/
int main() {
	 cin >>  n>> m>> c>>d;
	  //pre();
	  cal(c,d);
	  dfs(0,0);
	  cout <<ans;
}
2023/2/16 18:02
加载中...