40分dfs求助
查看原帖
40分dfs求助
600706
Ethereal_GG楼主2023/2/1 18:39
#include<iostream>
using namespace std;
long long ans;
int n , m;
int horx , hory;
int vis[1009][1009];
int fx[] = {0 , -2 , -2 , 2 , 2 , -1 , -1 , 1 , 1};
int fy[] = {0 , -1 , 1 , -1 , 1 , -2 , 2 , -2 , 2};
int dx[] = {0 , 0 , 1};
int dy[] = {0 , 1 , 0};
void dfs(int x , int y){
	if(x == n && y == m){
		ans++;
		return ;
	}
	for(int i = 1;i <= 2;i++){
		int newx = x + dx[i];
		int newy = y + dy[i];
		if(newx >= 1 && newx <= n && newy >= 1 && newy <= m && !vis[newx][newy]){
			vis[newx][newy] = 1;
			dfs(newx , newy);
			vis[newx][newy] = 0;
		}
	}
}
int main(){
	cin >> n >> m;
	cin >> horx >> hory;
	++n;
	++m;
	++horx;
	++hory;
	vis[horx][hory] = 1;
	for(int i = 1;i <= 8;i++)
		if(horx + fx[i] >= 1 && horx + fx[i] <= n && hory + fy[i] >= 1 && hory + fy[i] <= m) vis[horx + fx[i]][hory + fy[i]] = 1;
	dfs(1 , 1);
	cout << ans << endl;
	return 0;
}
2023/2/1 18:39
加载中...