题目链接: https://www.luogu.org/problemnew/show/P1443
题意:
给一个 n*m 的棋盘, 马在上面走 (规则就是象棋中的规则, 详细见代码 dx,dy 数组定义)
问棋盘上每个点马都需要走几步到达.
思路:
简单 bfs. 注意输出应该用 %-5d(不加空格)
- #include<stdio.h>
- #include<stdlib.h>
- #include<map>
- #include<set>
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- #include<vector>
- #include<queue>
- using namespace std;
- int n, m;
- struct node{
- int x, y;
- int step;
- }st;
- int mat[405][405];
- int dx[8] = {1, 1, 2, -2, 2, -2, -1, -1};
- int dy[8] = {2, -2, 1, 1, -1, -1, 2, -2};
- bool check(int i, int j)
- {
- return (i> 0 && i <= n && j> 0 && j <= m);
- }
- int main()
- {
- scanf("%d%d", &n, &m);
- scanf("%d%d", &st.x, &st.y);
- memset(mat, -1, sizeof(mat));
- st.step = 0;
- queue<node>que;
- que.push(st);
- mat[st.x][st.y] = 0;
- while(!que.empty()){
- node now = que.front();que.pop();
- node tmp;
- tmp.step = now.step + 1;
- for(int i = 0; i < 8; i++){
- tmp.x = now.x + dx[i];
- tmp.y = now.y + dy[i];
- if(check(tmp.x, tmp.y) && mat[tmp.x][tmp.y] == -1){
- mat[tmp.x][tmp.y] = tmp.step;
- que.push(tmp);
- }
- }
- }
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= m; j++){
- printf("%-5d", mat[i][j]);
- }
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2946519.html