BFS题,Atcoder上提交AC41WA16个,已写注释

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
struct node
{
	int x, y, d, step;//d 为1则这步垂直 为2则这步水平    step为步数
};
char arr[N][N];
int vis[N][N];
queue<node>q;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
signed main()
{
	int n, m;
	cin >> n >> m; 
	int bi, bj, ei, ej;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 'S')bi = i, bj = j;//记录开始坐标
			if (arr[i][j] == 'G')ei = i, ej = j;//记录目标坐标
		}
	
	q.push({bi,bj,1,0});//1垂直
	q.push({bi,bj,2,0});//2水平
	vis[bi][bj] = 1;
	while (!q.empty())
	{
		auto t = q.front();//t为目前位置
		q.pop();
		if (t.x == ei && t.y == ej)//如果到了目标位置
		{
			cout << t.step; return 0;
		}
		for (int i = 0; i < 4; i++)//i 0右 1下 2左 3上
		{
			if (t.d == 1 && (i == 1 || i == 3))continue;//如果上步为1垂直,则下一步不能走 下和上
			if (t.d == 2 && (i == 0 || i == 2))continue;//如果上步为2水平,则下一步不能走 左和右

				int a = t.x + dx[i], b = t.y + dy[i];//下一步的坐标 a为x坐标 b为y坐标
				if (a <= 0 || a > n || b <= 0 || b > m)continue;//越界
				if (vis[a][b])continue;//走过
				if (arr[a][b] =='#')continue;//有障碍物

				vis[a][b] = 1;
				if(i==1||i==3)//记录此步为垂直 
				q.push({ a,b,1,t.step+1});//步数+1
				if (i == 0 || i == 2)//记录此步为水平 
					q.push({ a,b,2,t.step + 1 });//步数+1
			}
	}
		cout << -1;
	return 0;
}