用dfs一直都是wr和超时,有大佬能帮忙看下吗
查看原帖
用dfs一直都是wr和超时,有大佬能帮忙看下吗
948229
tutu_6trc楼主2023/3/8 15:55
#include <bits/stdc++.h>
using namespace std;
int hx,hy,edx,edy;
int ans=0;
bool vis[50][50]={false};
int a[8]={1,1,-1,-1,2,2,-2,-2};
int b[8]={2,-2,-2,2,1,-1,1,-1};
int c[2]={1,0};
int d[2]={0,1};
bool valid(int x,int y){
	int flag=0;
	for(int i=0;i<8;i++){
		int nx=hx+a[i];
		int ny=hy+b[i];
		if(x==nx&&y==ny){
			flag=1;
			break;
		}
	}
	if(x==hx&&y==hy)
		flag=1;
	if(flag==0)
	return true;
	else
	return false;
}
void dfs(int x,int y){
	if(x==edx&&y==edy){
		ans++;
		return;
	}
	vis[x][y]==true;
	for(int i=0;i<2;i++){
		int newx=x+c[i];
		int newy=y+d[i];
		if(valid(newx,newy)==true&&vis[newx][newy]==false&&newx>=0&&newx<edx&&newy>=0&&newy<edy){
			dfs(newx,newy);		
		}
	}
	vis[x][y]=false;
}
int main(){
	cin>>edx>>edy>>hx>>hy;
	dfs(0,0);
	cout<<ans;
}
2023/3/8 15:55
加载中...