题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>


using namespace std;

const int N = 10;
int st[N][N];
int n, m;
int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1}, dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};

void dfs(int x, int y, int cnt, int &ans)
{
    if (cnt == n * m)
    {
        ans ++;
        return;
    }
    int res = 0;
    st[x][y] = true;
    for (int i = 0; i < 8; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || b < 0 || a >= n || b >= m) continue;
        if (st[a][b]) continue;
        dfs(a, b, cnt + 1, ans);
    }
    st[x][y] = false;

}

int main()
{
   int T;
   cin >> T;
   while(T --)
   {
       int x, y;
       cin >> n >> m >> x >> y;
       int ans = 0;
       dfs(x, y, 1, ans);
       cout << ans << endl;
   }
   return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>


using namespace std;

const int N = 10;
int st[N][N];
int n, m;
int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1}, dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};

int dfs(int x, int y, int cnt)
{
    if (cnt == n * m) return 1;
    int res = 0;
    st[x][y] = true;
    for (int i = 0; i < 8; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || b < 0 || a >= n || b >= m) continue;
        if (st[a][b]) continue;
        res += dfs(a, b, cnt + 1);
    }
    st[x][y] = false;
    return res;
}

int main()
{
   int T;
   cin >> T;
   while(T --)
   {
       int x, y;
       cin >> n >> m >> x >> y;

       cout << dfs(x, y, 1) << endl;
   }
   return 0;
}