当前位置: 代码迷 >> 综合 >> OpenJ_Bailian - 4123 马走日
  详细解决方案

OpenJ_Bailian - 4123 马走日

热度:20   发布时间:2023-12-08 08:18:21.0

#include <iostream>
#include <cstring>using namespace std;int t,n,m,x,y,cnt/*记录跳过的点*/,sum/*记录一共多少种情况可以跳满*/;
int vis[15][15];
int dx[8]= {1,2,-1,-1,1,-2,-2,2};//马走日跳的规则是日字形跳法,例如:x=1,y=2用dx[0]dy[0]来表示,x=-1,y=2用dx[2]dy[2]表示
int dy[8]= {2,1,2,-2,-2,1,-1,-1};void dfs(int a,int b)
{if(cnt==n*m-1){sum++;}for(int i=0; i<8; i++){int xx=a+dx[i];int yy=b+dy[i];if(!vis[xx][yy]&&xx>=0&&xx<n&&yy>=0&&yy<m)//保证这个位置之前没有跳到过,而且该点一定在格子里。{vis[xx][yy]=1;//标记该点已经跳过cnt++;//每次跳到一个点,记录一次,最终保证所有点跳过的条件就是cnt==n*m-1dfs(xx,yy);vis[xx][yy]=0;//如果不符合条件,步骤往后退,表示该点没有经过cnt--;//且跳过的点-1}}
}
int main()
{cin >> t;while(t--){cin >> n >> m >> x >> y;cnt=0,sum=0;memset(vis,0,sizeof vis);//因为是多组数据,一定一定要重置数组!!vis[x][y]=1;dfs(x,y);cout << sum << endl;}return 0;
}