dfs 回溯
回溯
:当前节点执行完,系统自动返回到上一次调用的函数里
- 回溯在代码是体现不出来的,是系统自动做优化的
- 在这道题里,回溯就是
悔棋
- 可以用全局变量统计方案数
- 需要恢复现场
- 有恢复现场不需要重置st数组,但是答案要重置
#include <iostream>
using namespace std;
const int N = 15;
int n, m, x, y;
bool st[N][N];
int ans;
int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
void dfs(int x, int y, int cnt)
{
if (cnt == n * m)//计算方案数
{
ans ++ ;
return;
}
st[x][y] = true;
for (int i = 0; i < 8; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (st[a][b]) continue;
dfs(a, b, cnt + 1);
}
st[x][y] = false;//恢复现场
}
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n >> m >> x >> y;
ans = 0;//每组数据答案重置
dfs(x, y, 1);
cout << ans << endl;
}
}