要做一个有心人——王晓燕

由于肺炎疫情的爆发，假期去学校机房上课的计划泡汤了

可是王主任早就给我们列好了计划 传统艺能

然后他就给我们整了一大堆题，其中就包含非常简单的搜索题

于是就有了这道简单的题目：

【题目描述】
马在中国象棋以日字形规则移动。

请编写一段程序，给定n×m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

【输入】
第一行为整数T(T < 10)，表示测试数据组数。

每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0≤x≤n-1,0≤y≤m-1, m < 10, n < 10)。

【输出】
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。

【输入样例】
1
5 4 0 0
【输出样例】
32

这道题思路比较简单

从起点开始按日字格走，当步数等于n*m的时候，就代表着遍历了一次，那么答案加一

于是就有了下面的代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int dx[]={0,1,1,2,2,-1,-1,-2,-2};
const int dy[]={0,2,-2,1,-1,2,-2,1,-1};
int t,ans=0,n,m,sx,sy;
bool vis[101][101];
void dfs(int x,int y,int cnt){
    if(cnt==n*m)ans++;
    else{
    for(int i=1;i<=8;++i){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(x>=0&&x<n&&y>=0&&y<m&&vis[tx][ty]==false){
            vis[tx][ty]=1;
            dfs(tx,ty,cnt+1);
            vis[tx][ty]=0;
        }
    }
    }
}
int main()
{
    cin>>t;
    for(int i=1;i<=t;++i){
        cin>>n>>m>>sx>>sy;
        dfs(sx,sy,1);
        cout<<ans<<endl;
        ans=0;
    }
    system("pause");
    return 0;
}

OK!编译运行，把样例复制上去，按下Enter，然后RE

！？RE，哪里出了问题？

通过仔细观察我们发现（jzh大佬说不能用肉眼看），在判断是否出界时候应该要用移动后的坐标tx,ty

打标也不太对，应当在当前坐标点处打标

这才有了真正的AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int dx[]={0,1,1,2,2,-1,-1,-2,-2};
const int dy[]={0,2,-2,1,-1,2,-2,1,-1};
int t,ans=0,n,m,sx,sy;
bool vis[101][101];
void dfs(int x,int y,int cnt){
    if(cnt==n*m)ans++;
    else{
    for(int i=1;i<=8;++i){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx>=0&&tx<n&&ty>=0&&ty<m&&vis[tx][ty]==false){
            vis[x][y]=1;
            dfs(tx,ty,cnt+1);
            vis[x][y]=0;
        }
    }
    }
}
int main()
{
    cin>>t;
    for(int i=1;i<=t;++i){
        cin>>n>>m>>sx>>sy;
        dfs(sx,sy,1);
        cout<<ans<<endl;
        ans=0;
    }
    system("pause");
    return 0;
}

这个故事告诉我们，要做一个有心人。不然就会和别人产生差距，是必定AK不了IOI的....