做法一，tle了，在于没有优化结束条件

#include <iostream>
#include <cstring>

using namespace std;

const int N=11;

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

int f()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(st[i][j]==0) return 0;
        }
    }
    return 1;
}
void dfs(int x,int y)
{

    if(f()==1)
    {
        res++;
    }

    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=0 && a<=n-1 &&b>=0 &&b<=m-1 && st[a][b]==0)
        {
            st[a][b]=1;
            dfs(a,b);
            st[a][b]=0;
        }
    }

}

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

    return 0;
}

算法二,多传入一个参数，优化了结束条件

#include <iostream>
#include <cstring>

using namespace std;

const int N=11;

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


void dfs(int x,int y,int cnt)
{

    if(cnt==n*m)
    {
        res++;
    }

    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=0 && a<=n-1 &&b>=0 &&b<=m-1 && st[a][b]==0)
        {
            st[a][b]=1;
            dfs(a,b,cnt+1);
            st[a][b]=0;
        }
    }

}

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

    return 0;
}

内部搜索：棋盘内部，某个点到另外一个点。所有点在棋盘内部，保证每个点只搜一次，不需要回复现场。

外部搜索：把整个棋盘看成一个状态，看能不能从一个状态变成另外一个状态

内部搜索不需要回复，外部搜索需要回复！！！

二刷

#include <iostream>
#include <cstring>

using namespace std;

const int N=11;

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


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

    return;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(st,0,sizeof st);
        res=0;
        int sx,sy;
        cin>>n>>m;
        cin>>sx>>sy;
        st[sx][sy]=1;
        dfs(sx,sy,1);
        cout<<res<<endl;
    }


    return 0;
}

三刷，过了

外部搜索，需要回复现场

#include <iostream>
#include <cstring>

using namespace std;

const int N=11;

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

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

    return;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        int sx,sy;
        cin>>sx>>sy;
        memset(st,0,sizeof st);
        res=0;
        st[sx+1][sy+1]=1;
        dfs(sx+1,sy+1,1);

        cout<<res<<endl;
    }
    return 0;
}

2023/12/1

没什么需要注意的，成功ac
记录方案数的，需要恢复现场

#include <iostream>
#include <cstring>

using namespace std;


const int N=30;

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

int sx,sy;

void dfs(int x, int y, int u)
{
    if(u == n*m)
    {
        res++;
        return;
    }

    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];

        if(a<0 || a>=n || b<0 || b>=m) continue;
        if(st[a][b]) continue;

        st[a][b] = 1;
        dfs(a, b, u+1);
        st[a][b] = 0;

    }
}

int main()
{
    cin>>T;
    while(T--)
    {
        res = 0;
        memset(st, 0, sizeof(st));
        cin>>n>>m>>sx>>sy;
        st[sx][sy] = 1;
        dfs(sx, sy, 1);


        cout<<res<<endl;

    }
    return 0;
}