题解 | #走迷宫#

标准的BFS板子
#include<iostream>
#include<queue>
using namespace std;

char arr[1001][1001];
bool visit[1001][1001];
int pos[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

struct Node {
	int x;
	int y;
	int length;
};

int BFS(int c_x, int c_y, int x, int y,int n,int m) {
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			visit[i][j] = false;
		}
	}
	queue<Node> pq;
	Node temp;
	temp.x = c_x;
	temp.y = c_y;
	temp.length = 0;
	visit[c_x][c_y] = true;
	pq.push(temp);
	while (pq.empty() == false) 
	{
		Node temp = pq.front();
		pq.pop();
		if (temp.x == x && temp.y == y) {
			return temp.length;
		}
		for (int i = 0; i < 4; i++) {
				if (arr[temp.x + pos[i][0]][temp.y + pos[i][1]] == '.' && visit[temp.x + pos[i][0]][temp.y + pos[i][1]]==false)
			{
				Node t;
				t.x = temp.x + pos[i][0];
				t.y = temp.y + pos[i][1];
				t.length = temp.length + 1;
				visit[t.x][t.y] = true;
				pq.push(t);
			}
		}
	}
	return -1;
}


int main() {
	int n, m;
	cin >> n >> m;
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	int res = BFS(x1,y1,x2,y2,n,m);
	cout << res << endl;
}