办一家建筑公司流程/seo chinaz
3149: 搜索基础之马走日
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 18 Solved: 12
[Submit][Status][Web Board]
Description
马在中国象棋以日字形规则移动。
请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。Input
第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 10, n < 10)
Output
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。
Sample Input
15 4 0 0
Sample Output
32
思路分析：马只能按日字型移动，在一点，它有八种不同的跳法，下过象棋的人都知道，也很容易可以将它的几种跳法用数学语言表示出来。这里建立两个数组分别表示X轴方向和Y轴方向的移动方向及距离。
只需要记录每一个它已经来过的位置，当最终经过所有点时，满足的ANS+1，由于在马跳之前进行了判断，它只能跳去以前没有去过的点，即马每成功跳一次必然经过一个新的点。
AC代码：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int m,n;//棋盘大小
int ax[8]={1,1,-1,-1,2,2,-2,-2};
int ay[8]={2,-2,2,-2,1,-1,1,-1};
int total,ans;
bool mark[1000][1000];
bool check (int x,int y)//检查此位置是否合法
{if(x<n&&y<m&&x>=0&&y>=0)return true;elsereturn false;
}
void search(int x,int y)
{int i;for(i=0;i<8;i++)if(check(x+ax[i],y+ay[i])&&!mark[x+ax[i]][y+ay[i]])//此位置合法且以前没有跳过{mark[x+ax[i]][y+ay[i]]=true;total++;//记录跳的此数，即经过点的次数。if(total==n*m-1)//遍历完棋盘上所有点ans++;//一个正确路径search(x+ax[i],y+ay[i]);//回溯total--;mark[x+ax[i]][y+ay[i]]=false;}
}
int main()
{int t;//t组测试数据int x,y;scanf("%d",&t);while(t--){ans=total=0;//全局变量值会保存下来memset(mark,0,sizeof(mark));scanf("%d %d %d %d",&n,&m,&x,&y);if(!check(x,y))printf("0\n");else if(n==1&&m==1)printf("1\n");else{mark[x][y]=true;//标记起点search(x,y);printf("%d\n",ans);}}return 0;
}