题解：首先肯定是bfs和dfs来比较一下，题目是说有多少种路径，那么这样的话bfs肯定不好找，就用dfs来找，找的话vis的作用就很重要了，它标记过已经走过了的，避免死循环，而且回溯的时候重新置为0，这样的话如果有新的路径也不耽误。
#include <iostream> #include <cstring> using namespace std; const int N = 11; int vis[N][N], n, m, x0, y0, nm, ans = 0; int dir[8][2] = {{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}}; void dfs(int x, int y, int steps) { if (steps == nm) { ans++; return; } else { for (int i = 0; i < 8; ++i) { int tmpx = x + dir[i][0]; int tmpy = y + dir[i][1]; if (tmpx >= 0 && tmpy >= 0 && tmpx < n && tmpy < m && !vis[tmpx][tmpy]) { vis[tmpx][tmpy] = 1; dfs(tmpx, tmpy, steps + 1); vis[tmpx][tmpy] = 0; } } } } int main() { int t; scanf("%d", &t); while (t--) { memset(vis, 0, sizeof(vis)); scanf("%d%d%d%d", &n, &m, &x0, &y0); nm = n * m, ans = 0; vis[x0][y0] = 1; dfs(x0, y0, 1); printf("%d\n", ans); } return 0; }
