题目描述
有一个n \times mn×m棋盘，在某一点(x, y)(x,y)上面有一匹马，要求你至少要走几步才能计算出马到达棋盘上的任何一个点。
输入格式
输入只有一行四个整数n, m, x, yn,m,x,y。
输出格式
一个n \times mn×m矩阵，代表马到达某一点至少要走几步(左对齐，宽55如果无法到达，则输出-1?1）。
输入输出样例
复制
3 3 1 1
复制
0 3 2 3 -1 1 2 1 4
说明/提示
数据规模与约定
对于全部的测试点，保证1 \leq x \leq n \leq 4001≤x≤n≤400，1 \leq y \leq m \leq 4001≤y≤m≤400。
思路：这是一个寻求最短路径的问题，所以它有八个扩展方向 ，与走迷宫寻找最短路径的本质相同，每次循环，深度加一。
一个二维数组首先初始化，所有元素为-1（x，y）0，然后开始bfs搜索，每次进入一层，深度加一层，深度就是步数，这一层的扩展点就是这个步数，直到队列中没有元素，整个二维数组完成处理，安装要求输出。
代码如下(注意事项已注明)
#include<stdio.h> #include<string.h> int n,m; int mp[410][410] int book[410][410] ///学新招就是自定义check函数检查是否越界 //而且以越界条件先判断好像可以节省时间 //(因为只要一个条件不满足，就是越界) ///不需要判断不越界的条件是否符合要求 int check(int x,int y) { if(x<1||x>n||y<1||y>m)//注意噢x>n和y<m,不要都写成n，棋盘范围是n*m而不是n*n return 0; return 1.//返回1或0以后方便if条件判断 } /*起初，潜意识地认为只有四个定义的方向 数组是next[4][2]后来不记得改成了 8.答案奇怪离谱，找了很久(真的找到了) 久呜呜)其实是这里的问题，麻了麻了... int next[8][2]= {
{2,1}, //下右日 {2，-1} {2，1} {2，-1} {1，2} {-1，2} {1，-2} {-1,-2} };//左上日 struct queue//因为是bfs，要用到队列结构体 { int x; int y; } que[160001]*400 void bfs(int x,int y)//注意广度优先搜索 { int head=0,tail=1; int sum=0；///步数清零 ///初始点入队 que[1].x=x; que[1].y=y; //标记初始点 book[x][y]=1; mp[x][y]=0; while(head<tail) { head ; sum=mp[que[head].x][que[head].y] 1；///后扩展成功的点深加一 for(int i=0; i<8; i )///从这个点到每个方向 { int ax=que[head].x next[i][0]; int ay=que[head].y next[i][1]; if(check(ax,ay)&&book[ax][ay] == 0)//如果没有达到，将其入队 { tail ; que[tail].x=ax; que[tail].y=ay; book[ax][ay]=1; mp[ax][ay]=sum;///符合要求的点步数等于sum } //如果没有进入if判断句不符合要求，通过for下一点可以循环扩展 } } } int main() { int x,y; scanf("%d %d %d %d",&n,&m,&x,&y); memset(mp,-1,sizeof(mp));// bfs(x,y); //输出结果 for(int i=1; i<=n; i ) { for(int j=1; j<=m; j ) { printf("%-5d",mp[i][j]);//一定不要下意识地在d后面添加空间！！！！血的教训呜呜 } if(i!=n) printf("\n"); } return 0; }