C++ - 计蒜客 - 大钉骑马走江湖(bfs)_综合

江湖是什么，对于在象棋界厮杀的大钉来说，江湖就是一个矩阵，他的目标，就是在江湖之中骑着马，从他的位置出发，走到终点。

当然，大钉的马也遵从中国象棋中的“马走日”的规则，而且在矩阵中，也会有一些障碍物，马不能跳到障碍物上；如果大钉的马面前有障碍物，即被“别马腿”，那么他将不能跳向有障碍物的左前和右前这两个方向。

请问最少需要多少步，大钉才能骑着马跳到终点。

输入格式：

有多组测试样例。

每组第一行输入两个数 $n$ 和 $m$ ，代表矩阵的行数和列数， $\leq n \leq m < 100$ 。

接下来输入 $n$ 行字符串，其中 's' 代表起点，'e' 代表终点，'.' 代表空地，'#' 代表障碍物。

输出格式：

对应每组输入，输出骑马跳到终点的最小步数，如果跳不到终点，输出 $? 1$ 。

样例输入

3 3
s..
...
..e3 3
s#.
...
#.e

样例输出

4
-1

广度优先搜索bfs,从起点搜索,直到搜到终点，题目增加了障碍物，入队前另外判断是否别马腿和是否跳到的位置有障碍物。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
int n,m,x1,y1,x2,y2,flag;
char map[104][104];
int vis[104][104];
int dir[8][2] = {  //8个方向 1,2,2,1,2,-1,1,-2,-1,-2,-2,-1,-2,1,-1,2  
}; 
struct point{int x,y,s;
};void bfs(){queue<point> q;point p;p.x = x1;p.y = y1;p.s = 0;vis[p.x][p.y] = 1;q.push(p);//起点 while(!q.empty()){point p = q.front();//当前点是终点//1.起点等于终点//2.终点非起点 if(p.x==x2 && p.y==y2){if(p.s==0){break;}printf("%d\n",p.s);flag = 1;break;}point v;//用来存储下一个点 for(int i=0 ;i<8 ;i++){v.x = p.x + dir[i][0];v.y = p.y + dir[i][1];int bx = p.x + dir[i][0]/2;int by = p.y + dir[i][1]/2;if(map[bx][by]=='#'){//别马腿 continue;}if(v.x>=0 && v.x<n && v.y>=0 && v.y<m && map[v.x][v.y]!='#' && vis[v.x][v.y]==0){v.s = p.s+1;q.push(v);//讲合法的点入队 vis[v.x][v.y] = 1;//标记已访问 }}q.pop();}if(flag==0){//无法走到终点的情况 printf("-1\n");}	
}int main(){while(cin>>n>>m){memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));for(int i=0 ;i<n ;i++){for(int j=0 ;j< m ;j++){cin>>map[i][j];if(map[i][j]=='s'){//起点 x1 = i;y1 = j;}if(map[i][j]=='e'){//终点 x2 = i;y2 = j;}		}}flag = 0;//每组数据清零 bfs();}return 0;
}