马的遍历
输出的是在nXm的棋盘上，从某一个到棋盘上任意一个点的最少步数，永远到不了的地方为-1.
这道题我也只是做对了一部分，但我觉得有些收获。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
const int N = 410;
typedef pair<int, int> PIL;
int n, m;
int dist[N][N];
PIL q[N * N];
int dx[] = { 2,2,1,1,-1,-1,-2,-2 };
int dy[] = { 1,-1,2,-2,2,-2,1,-2 };
void bfs(int x1,int y1)
{memset(dist, -1, sizeof(dist));q[0] = { x1,y1 };dist[x1][y1] = 0;int hh = 0, tt = 0;//h为头指针，t为尾指针while (hh <= tt){auto t = q[hh];//取出队头，相当于t=q.front()hh++; //q.pop()for (int i = 0; i < 8; i++){int a = t.x + dx[i];int b = t.y + dy[i];if (a<1 || a>n || b<1 || b>m)continue;if (dist[a][b]>=0)continue;dist[a][b] = dist[t.x][t.y] + 1;q[++tt] = { a,b };}}
}
int main()
{int x1, y1;scanf("%d%d%d%d", &n, &m, &x1, &y1);bfs(x1, y1);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){printf("%d ", dist[i][j]);}printf("\n");}return 0;
}第一个就是减少用cin和cout来输入和输出。因为数据超过1e5的时候，输入和输出会比scanf和printf慢。然后了解了一个快读函数。
int read()
{int x = 0, f = 1;char c = getchar();while (c < '0' || c>'9') {if (c == '-')f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}return x * f;
}这个函数后半截之前也模拟过，把字符型转换。
第二个就是用数组模拟队列。
1.先定义两个int变量head，tail。其作用相当于指针。通常先赋值为had=0，tail=0或-1.
2.如何表示插入队列的操作？就是数组a【tail++】=x，x为要插入的数字
3.模拟队列弹出的操作，head++。
4.表示队列不为空的操作，while（head<=tail）.
离开中山路
bfs。为什么会用队列？
先用一个结构体储存横纵坐标，压入队列。如果队列不为空，执行以下操作
1.取出第一个数，判断四个方向可不可以走
2.如果可以走，把它横纵坐标存入队列里。
3.步数加一。
还要一个二维数组储存步数。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1005;
struct node
{int x, y;
};
queue<node>q;
int ans[N][N];
char a[N][N];
int walk[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int main()
{int n, x1, y1, x2, y2;memset(ans, -1, sizeof(ans));cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> a[i][j];}}cin >> x1 >> y1 >> x2 >> y2;node tmp = { x1,y1 };q.push(tmp);ans[x1][y1] = 0;while (!q.empty()){node u = q.front();int ux = u.x;int uy = u.y;q.pop();for (int i = 0; i <= 3; i++){int x = ux + walk[i][0], y = uy + walk[i][1];int d = ans[ux][uy];if (x<1 || x>n || y<1 || y>n || ans[x][y] != -1 || a[x][y] == '1')continue;ans[x][y] = d + 1;node tmp = { x,y };q.push(tmp);}}cout << ans[x2][y2];return 0;
}
