学习总结三十六

马的遍历

输出的是在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;
}