题解 | 走迷宫

#include <iostream>
#include <queue> 
#include <string>
#include <cstring>

using namespace std;

struct Grid {
	int x;
	int y;
	int cost;
};

int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int vis[1000][1000];
char c[1005][1005];

//记录一下C++的char数组输入
//1.使用cin.getline(buffer, m + 1)会读取m个字符并末尾补充'\0'，这个buffer支持静态（可以大于输入大小）和动态大小
//2.可以使用getline(cin, string), strcpy(char*, string.c_str()) 
int main() {
	int n, m, s_x, s_y, e_x, e_y;  
	cin >> n >> m >> s_x >> s_y >> e_x >> e_y;
	s_x--;
	s_y--;
	e_x--;
	e_y--;
	cin.ignore();
	string s;
//	char** c = new char*[n]; 
	for (int i = 0; i < n; i++) {
//		c[i] = new char[m + 1];动态数组
//		cin.getline(c[i], m + 1);
		
		//下面是使用c_str
		getline(cin, s);
		const char* cs = s.c_str();
		strcpy(c[i], cs);
	}
//	for (int i = 0; i < n; i++) {
//		for (int j = 0; j < m; j++) {
//			cout << c[i][j] << " ";
//		}
//		cout << endl;
//	}
	int ans = -1;
	if (c[s_x][s_y] != '*' && c[e_x][e_y] != '*') {
		queue<Grid> q;
		Grid st;
		st.x = s_x;
		st.y = s_y;
		st.cost = 0;
		q.push(st);
		vis[st.x][st.y] = 1;
		bool flag = false;
		while (!q.empty()) {
			Grid g = q.front();
			q.pop();
			for (int i = 0; i < 4; i++) {
				int x = g.x + direction[i][0];
				int y = g.y + direction[i][1];
				if (x >= 0 && x < n && y >= 0 && y < m && c[x][y] != '*' && !vis[x][y]) {
					int new_cost = g.cost + 1;
					if (x == e_x && y == e_y) {
						flag = true;
						ans = new_cost;
						break;
					}
					Grid new_grid ;
					new_grid.x = x;
					new_grid.y = y;
					new_grid.cost = new_cost;
					q.push(new_grid);
					vis[x][y] = 1;
				}
			}
			if (flag) break;
//			queue<Grid> q2 = q;
//			while (!q2.empty()) {
//				Grid g = q2.front();
//				cout << "{" << g.x << "," << g.y << "," << g.cost << "} "; 
//				q2.pop();
//			}
//			cout << endl;
		}	
	}
	cout << ans << endl;
}