马走日不知哪里出错了,求指点出错误,不要直接给答案代码,感谢
8465:马走日
查看提交统计提问
总时间限制: 1000ms 内存限制: 65536kB
描述
马在中国象棋以日字形规则移动。
请编写一段程序,给定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
#include
#include
int vis[11][11]={0};
int n,m,cnt;
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
void dfs(int x,int y,int dep) {
printf("%d %d %d\n",x,y,dep);
if(dep==n*m){
cnt++;
return ;
}
int i;
for(i=0;i<8;i++){
int bx=x+dx[i],by=y+dy[i];
if(bx<0||bx>=n||by<0||by>=m)continue;
if(vis[bx][by])continue;
vis[bx][by]=1;
dfs(bx,by,dep+1);
vis[bx][by]=0;
}
}
int main()
{
int t,x,y;
scanf("%d",&t) ;
while(t--){
scanf("%d%d%d%d",&n,&m,&x,&y);
cnt=0;
memset(vis,0,sizeof(vis)) ;
vis[x][y]=1;
dfs(x,y,0);
printf("%d\n",cnt);
}
return 0;
}
import java.util.Scanner;
public class Main {
static boolean[][] vis; // 标记数组
static int[] orient = {-1, 2, 1, -2, -1, -2, 1, 2, -1}; // 8个方向
static int sum, n, m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
// 矩阵图大小
n = sc.nextInt();
m = sc.nextInt();
// 初始化标记数组,默认false
vis = new boolean[n][m];
// 获取起点坐标
int x = sc.nextInt();
int y = sc.nextInt();
// 初始化,方案总数
sum = 0;
// 标记起点位置已经访问
vis[x][y] = true;
// 深度优先搜索:Go!
dfs(x, y, 1);
// 打印结果
System.out.println(sum);
}
}
public static void dfs(int x, int y, int curSum) {
// 如果遍历完全部点,方案数 sum++,递归终止条件
if (curSum == (n * m)) {
sum++;
return;
}
// 递归8个方向
for (int i = 0; i < 8; i++) {
// 获取可以到达的新方向
int u = x + orient[i];
int v = y + orient[i+1];
// 剪枝条件,避免无效递归
if (u < 0 || u >= n || v < 0 || v >= m || vis[u][v])
continue;
// 标记当前位置已访问
vis[u][v] = true;
// 继续往深处递归
dfs(u, v, curSum+1);
// 回溯
vis[u][v] = false;
}
}
}
#include<stdio.h>
#include<stdbool.h>
int u[8]={-1,1,-2,2,-2,2,-1,1};
int v[8]={2,2,1,1,-1,-1,-2,-2};
int num=0;//路径总数及记录
int a[11][11]={0};//记录每一步走在哪一个格子
_Bool b[11][11]={0}; //记录走没走过这个点
void search(int x,int y,int n,int m,int k);//运算的函数,ab是初始位置,nm是棋盘的长宽,k为循环的次数
int main()
{
int t;
int n,m,x,y;
scanf("%d",&t);//测试的组数
for(t;t>0;t--){
scanf("%d %d %d %d",&n,&m,&x,&y);
b[x][y]=1;//第一个点已经被踩过了要标注上啊喂!!
search(x,y,n,m,2);
printf("%d\n",num);
}
return 0;
}
void search(int x,int y,int n,int m,int k)//初始x,y n行m列 第k次循环
{
int xx,yy,i;
if(k>n*m)
{
num++;
return;
}
for(i=0;i<8;i++)//遍历8个方向,每个方向试一次
{
xx=x+u[i];
yy=y+v[i];
if(xx<=n-1 && xx>=0 && yy<=m-1 && yy>=0 && !(b[xx][yy]))
{
b[xx][yy]=1;//标记走过了
a[xx][yy]=k;//走的第c步
search(xx,yy,n,m,k+1);
b[xx][yy]=0;
a[xx][yy]=0;
//不太明白的恢复:回溯的时候把标记清除,以便选择另一条途径
}
}
}