洛谷1443 马的遍历【bfs】
题目链接：https://www.luogu.org/problemnew/show/P1443
题意：
给一个n*m的棋盘，马在上面走（规则就是象棋中的规则，详细见代码dx，dy数组定义）
问棋盘上每个点马都需要走几步到达。
思路：
简单bfs。注意输出应该用%-5d（不加空格）
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<map> 4 #include<set> 5 #include<iostream> 6 #include<cstring> 7 #include<algorithm> 8 #include<vector> 9 #include<queue> 10 11 using namespace std; 12 13 int n, m; 14 struct node{ 15 int x, y; 16 int step; 17 }st; 18 int mat[405][405]; 19 20 int dx[8] = {1, 1, 2, -2, 2, -2, -1, -1}; 21 int dy[8] = {2, -2, 1, 1, -1, -1, 2, -2}; 22 23 bool check(int i, int j) 24 { 25 return (i > 0 && i <= n && j > 0 && j <= m); 26 } 27 28 int main() 29 { 30 scanf("%d%d", &n, &m); 31 scanf("%d%d", &st.x, &st.y); 32 memset(mat, -1, sizeof(mat)); 33 st.step = 0; 34 queue<node>que; 35 que.push(st); 36 mat[st.x][st.y] = 0; 37 while(!que.empty()){ 38 node now = que.front();que.pop(); 39 node tmp; 40 tmp.step = now.step + 1; 41 for(int i = 0; i < 8; i++){ 42 tmp.x = now.x + dx[i]; 43 tmp.y = now.y + dy[i]; 44 if(check(tmp.x, tmp.y) && mat[tmp.x][tmp.y] == -1){ 45 mat[tmp.x][tmp.y] = tmp.step; 46 que.push(tmp); 47 } 48 } 49 } 50 for(int i = 1; i <= n; i++){ 51 for(int j = 1; j <= m; j++){ 52 printf("%-5d", mat[i][j]); 53 } 54 printf(" "); 55 } 56 57 return 0; 58 }