You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
42 lines
1.1 KiB
42 lines
1.1 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 10;
|
|
int n, m;
|
|
int res;
|
|
int dx[] = {2, 2, 1, -1, -2, -2, 1, -1};
|
|
int dy[] = {1, -1, 2, 2, 1, -1, -2, -2}; // 进行移动
|
|
bool st[N][N]; // 判断该数是否被标记过
|
|
|
|
// 马走日的回溯法实现
|
|
void dfs(int x, int y, int cnt) {
|
|
if (cnt == n * m) {
|
|
res++;
|
|
return;
|
|
}
|
|
|
|
for (int i = 0; i < 8; i++) {
|
|
int tx = x + dx[i], ty = y + dy[i];
|
|
if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;
|
|
if (st[tx][ty]) continue;
|
|
|
|
st[tx][ty] = 1;
|
|
dfs(tx, ty, cnt + 1);
|
|
st[tx][ty] = 0;
|
|
}
|
|
}
|
|
int main() {
|
|
int T;
|
|
cin >> T;
|
|
while (T--) { // 多组测试数据
|
|
res = 0;
|
|
memset(st, 0, sizeof st);
|
|
|
|
int x, y; // 初始位置坐标
|
|
cin >> n >> m >> x >> y;
|
|
|
|
st[x][y] = 1; // 标记起点
|
|
dfs(x, y, 1);
|
|
st[x][y] = 0; // 其实，出发点是否回溯无所谓，不会对其它人造成影响,而且，下一轮开始时有清空操作
|
|
cout << res << endl;
|
|
}
|
|
} |