@[LgFvm9353](/user/1170547) 应该可以，你超时可能是因为忘记判断重复路线了
by danlao @ 2024-01-24 20:49:05
这样还是超时的
```c
#include<stdio.h>
int n, m, mx, my, ans;
int book[900][900];
int next[2][2] = { {1,0},{0,1} };
int nn[9][2] = { {0,0},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-1,2},{-2,1} };
void dfs(int x, int y) {
int tx, ty;
if (x == n && y == m) ans++;
for (int i = 0; i <= 1; i++) {
tx = x + next[i][0];
ty = y + next[i][1];
if (tx<0 || ty<0 || tx>n || ty>m) {
continue;
}
//int flag = 0;
//for (int j = 0; j <= 8; j++) {
// if (tx == mx + nn[j][0] && ty == my + nn[j][1]) {
// flag = 1;
// break;
// }
//}
if (tx == mx && ty == my || tx == mx + 1 && ty == my + 2 || tx == mx + 2 && ty == my + 1 || tx == mx + 2 && ty == my - 1 || tx == mx + 1 && ty == my - 2 || tx == mx - 1 && ty == my - 2 || tx == mx - 2 && ty == my - 1 || tx == mx - 1 && ty == my + 2 || tx == mx - 2 && ty == my + 1) {
continue;
}
// if (flag == 1) continue;
if (book[tx][ty] == 0) {
book[tx][ty] = 1;
dfs(tx, ty);
book[tx][ty] = 0;
}
}
return;
}
int main() {
scanf("%d %d %d %d", &n, &m, &mx, &my);
n += 2; m += 2; mx += 2; my += 2;
dfs(2, 2);
book[2][2] = 1;
printf("%d\n", ans);
return 0;
}
```
by LgFvm9353 @ 2024-01-24 21:09:16
@[yaodiguoan](/user/1023793)
by LgFvm9353 @ 2024-01-24 21:10:01
@[LgFvm9353](/user/1170547) 这道题搜索确实能过,但也需要用记忆化搜索,也就和DP差不多了,如果直接暴搜的话确实要超时(最多可能运算 $2^{381}$ 次).
by Whycmd @ 2024-01-24 21:17:26