马走日的解法（dfs）

佚名 4年前 (2020-01-28) 算法 974人围观抢沙发百度已收录

马在中国象棋以日字形规则移动。

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input

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

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

Output

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

1
5 4 0 0

Sample Output

32

马走日，4个方向换成8个方向深搜

代码：

#include<iostream>
using namespace std;
int n,m,x,y;
int cnt;
int vis[10][10];
int dx[]={2,-2,1,-1,2,-2,1,-1};
int dy[]={1,1,2,2,-1,-1,-2,-2};
void dfs(int x,int y,int t){
     if(t==n*m-1){
         cnt++;
         return;
     }
     for(int i=0;i<8;i++){
         int xx=x+dx[i];
         int yy=y+dy[i];
         if(xx<0||yy<0||xx>=n||yy>=m) continue;
         if(vis[xx][yy]) continue;
         vis[xx][yy]=true;
         dfs(xx,yy,t+1);
         vis[xx][yy]=false;
     }
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>x>>y;
        for(int i=0;i<n;i++)
          for(int j=0;j<m;j++)
             vis[i][j]=false;
        cnt=0;
        vis[x][y]=true;
        dfs(x,y,0);
        cout<<cnt<<endl;
    }    
    return 0;
}