P1443 马的遍历
输入输出样例
输入 #1复制
3 3 1 1
输出 #1复制
0 3 2
3 -1 1
2 1 4
总结目录
1 本题搜索思路，搜索路径去重方法 2 本题特点
1 搜索思路与去重
本题中，搜索的是最短路径，因此用BFS没有问题。另外，这里去除重复搜索的方法类似于机器人搬运重物。都是通过判断是否能够更新最短路来防止重复的搜索。只是机器人搬运重物那里是机器人走的方向和步数的结合，而这里是马的遍历的方向不同，但是步数固定
2 本题特点
本题特点一个是马的走路方式比较特别，因此设置了8个方向。另外就是输出方式使用了printf"%-5d"来进行对齐。
代码
#include<iostream>
#include<climits>
#include<algorithm>
#include<queue>
#define maxsize 405
using namespace std;
int mat[maxsize][maxsize];
int n, m;
int srow, scol;
int rowcol_change[][2] = {
{-1,2},//上右
{-2,1},
{-1,-2},//上左
{-2,-1},
{2,1},//下右
{1,2},
{2,-1},//下左
{1,-2}
};
struct node {
int row;
int col;
int step;
};
bool pace(node tmp, int k) {
//判断tmp状态能否按照k方向前进
int nextrow = tmp.row + rowcol_change[k][0];
int nextcol = tmp.col + rowcol_change[k][1];
if (nextrow >= 1 && nextrow <= n&&nextcol >= 1 && nextcol <= m) {//越界判断
return true;
}
return false;
}
void bfs(int row, int col) {
node start;
start.row = row;
start.col = col;
start.step = 0;
mat[row][col] = 0;
queue<node> q;
q.push(start);
while (!q.empty()) {
node tmp = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
if (pace(tmp, i)) {//如果当前方向可以到达那个点
int nextrow = tmp.row + rowcol_change[i][0];
int nextcol = tmp.col + rowcol_change[i][1];
if (tmp.step + 1 < mat[nextrow][nextcol]) {//如果这个走法可以更新
mat[nextrow][nextcol] = tmp.step + 1;
node tmp2;
tmp2.row = nextrow;
tmp2.col = nextcol;
tmp2.step = tmp.step + 1;
q.push(tmp2);
}
}
}
}
}
void disp() {
for (int row = 1; row <= n; row++) {
for (int col = 1; col <= m; col++) {
if (mat[row][col] == INT_MAX) {
printf("%-5d", -1);
}
else {
printf("%-5d", mat[row][col]);
}
}
cout << endl;
}
}
int main() {
cin >> n >> m;
cin >> srow >> scol;
fill(mat[0], mat[0]+maxsize*maxsize, INT_MAX);
bfs(srow, scol);
disp();
return 0;
}
