首页 > 代码库 > 1443 马的遍历
1443 马的遍历
难度：普及/提高-
题目类型：BFS
提交次数：5
涉及知识：BFS
题目描述
有一个n*m的棋盘(1<n,m<=200)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入输出格式
输入格式：
一行四个数据，棋盘的大小和马的坐标
输出格式：
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
代码：
#include<iostream>#include<queue>#include<cstring>#include<cstdio>using namespace std;int n, m, sx, sy;int d[2][8] = {{1, 1, -1, -1, 2, 2, -2, -2}, {2, -2, 2, -2, 1, -1, 1, -1}};int a[2001][2001];int visited[2001][2001];struct pos{ int x, y, step; pos(int xx, int yy, int s): x(xx), y(yy), step(s){}};bool check(int x, int y){ if(x>=1&&x<=n&&y>=1&&y<=m&&visited[x][y]==-1) return true; return false;}queue<pos>q;int main(){ cin>>n>>m>>sx>>sy; memset(visited, -1, sizeof(visited)); int i, j; q.push(pos(sx, sy, 0)); visited[sx][sy] = 0; while(!q.empty()){ pos p = q.front(); for(i = 0; i < 8; i++){ if(check(p.x+d[0][i], p.y+d[1][i])){ q.push(pos(p.x+d[0][i], p.y+d[1][i], p.step+1)); visited[p.x+d[0][i]][p.y+d[1][i]] = p.step+1; } } q.pop(); } for(i = 1; i <= n; i++){ for(j = 1; j <= m; j++) printf("%-5d", visited[i][j]); cout<<endl; } return 0;}
备注：
赤裸裸的BFS水题。但我居然又卡了半天。。本来是为了简化代码用了方向数组，结果visited加到了pop前 循环后，然后就各种超时，想了半天也没想明白。然而神奇的是当我刚开始给老师发微信的时候，看到了visited那行，发现不太对。。应该加到队列里的时候就做标记的啊。。不然又会拓展到它自己，不出问题才怪呢。到这里BFS告一段落了，打卡！
1443 马的遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。