算法 DFS

自己把递归的u装进去的时候是0, 递归判断终止条件为 u == n * m 后来才想不对

因为递归的时候已经有一个点填进去了，因该赋值为1才对。~~~

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10;

bool st[N][N];
int n, m, x, y;
int ans;
int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

void dfs(int x, int y, int u)
{
    if(u == n * m)
    {
        ans ++;
        return ;
    }
    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;
        st[a][b] = true;
        dfs(a, b, u + 1);
        st[a][b] = false;
    }
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        memset(st, false, sizeof st);
        cin >> n >> m >> x >> y;
        st[x][y] = true;
        dfs(x, y, 1);
        cout << ans << endl;
        ans = 0;
    }
    return 0;
}