60分TLE求调

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 5000

int ex, ey, x, y, sum;
int vis[N][N];
int dx[2] = {1, 0};
int dy[2] = {0, 1};

void dfs(int sx, int sy) {
	if (sx == ex && sy == ey) {
		sum++;
		return;
	}
	for (int i = 0; i < 2; i++) {
		int nx = sx + dx[i];
		int ny = sy + dy[i];
		if (nx >= 0 && ny >= 0 && nx <= ex && ny <= ey && !vis[nx][ny]) {
			vis[nx][ny] = 1;
			dfs(nx, ny);
			vis[nx][ny] = 0;
		}
	}
}

signed main() {
	cin >> ex >> ey >> x >> y;
	vis[x][y] = 1;
	int horse_dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
	int horse_dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
	for (int i = 0; i < 8; i++) {
		int nx = x + horse_dx[i];
		int ny = y + horse_dy[i];
		if (nx >= 0 && ny >= 0 && nx <= ex && ny <= ey) {
			vis[nx][ny] = 1;
		}
	}
	dfs(0, 0);
	cout << sum << endl;
	return 0;
}