Snaky Walk

Problem Statement

You are given a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left.

Each cell is one of the following: a start cell, a goal cell, an empty cell, or an obstacle cell. This information is described by $H$ strings $S_1,S_2,\dots,S_H$, each of length $W$. Specifically, the cell $(i,j)$ is a start cell if the $j$-th character of $S_i$ is S, a goal cell if it is G, an empty cell if it is ., and an obstacle cell if it is #. It is guaranteed that there is exactly one start cell and exactly one goal cell.

You are currently on the start cell. Your objective is to reach the goal cell by repeatedly moving to a cell adjacent by an edge to the one you are in. However, you cannot move onto an obstacle cell or move outside the grid, and you must alternate between moving vertically and moving horizontally each time. (The direction of the first move can be chosen arbitrarily.)

Determine if it is possible to reach the goal cell. If it is, find the minimum number of moves required.

More formally, check if there exists a sequence of cells $(i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)$ satisfying all of the following conditions. If such a sequence exists, find the minimum value of $k-1$.

For every $1 \leq l \leq k$, it holds that $1 \leq i_l \leq H$ and $1 \leq j_l \leq W$, and $(i_l,j_l)$ is not an obstacle cell.
$(i_1,j_1)$ is the start cell.
$(i_k,j_k)$ is the goal cell.
For every $1 \leq l \leq k-1$, $|i_l - i_{l+1}| + |j_l - j_{l+1}| = 1$.
For every $1 \leq l \leq k-2$, if $i_l \neq i_{l+1}$, then $i_{l+1} = i_{l+2}$.
For every $1 \leq l \leq k-2$, if $j_l \neq j_{l+1}$, then $j_{l+1} = j_{l+2}$.

Constraints

$1 \leq H,W \leq 1000$
$H$ and $W$ are integers.
Each $S_i$ is a string of length $W$ consisting of S, G, ., #.
There is exactly one start cell and exactly one goal cell.

Input

The input is given from Standard Input in the following format:

$H$ $W$

$S_1$

$S_2$

$\vdots$

$S_H$

Output

If it is possible to reach the goal cell, print the minimum number of moves. Otherwise, print -1.

Solving

The following code was compiled by using C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90


#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using ll = long long;
const int N = 1001;
int n,m;
bool check(int x,int y)//检查是否越界
{
    return x >= 0 && x < n && y >= 0 && y < m;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin >> n >> m;
    string grid[n];//定义字符串数组
    int sx,sy,ex,ey;
    for(int i = 0;i<n;i++)
    {
        cin >> grid[i];
        for(int j=0;j<m;j++)
        {
            if(grid[i][j]=='S')
            {
                sx = i;
                sy = j;
            }
            else if(grid[i][j]=='G')
            {
                ex = i;
                ey = j;
            }
        }
    }
    auto bfs = [&]() {
    bool vis[n][m][2];//创建三维布尔数组，第三位用于存储到达此点时的移动方向 0 为水平到达 1 为垂直到达
    memset(vis, 0, sizeof(vis));//记得初始化vis数组
    queue<vector<int>> q；
    q.push({sx,sy,-1,0});//start x ; start y ; Prev Status ; steps
    //入队前记得更新起点的状态
    vis[sx][sy][1] = true;
    vis[sx][sy][0] = true;
    while(!q.empty())
    {   
        int now_x = q.front()[0];
        int now_y = q.front()[1];
        int prevdir = q.front()[2];
        int steps = q.front()[3];
        q.pop();//读取完信息直接出队
        if(now_x==ex && now_y==ey)
        {   
            return steps;
        }
        //之前垂直方向移动
        if(prevdir != 0)
        {
            int nx = now_x + 1;
            if(check(nx,now_y)&&grid[nx][now_y]!='#'&&!vis[nx][now_y][0])
            {
                vis[nx][now_y][0] = true;
                q.push({nx,now_y,0,steps+1});
            }
            int nx2 = now_x - 1;
            if(check(nx2,now_y)&&grid[nx2][now_y]!='#'&&!vis[nx2][now_y][0])
            {
                vis[nx2][now_y][0] = true;
                q.push({nx2,now_y,0,steps+1});
            }
        }
        //之前水平方向移动
         if(prevdir != 1)
        {
            int ny = now_y + 1;
            if(check(now_x,ny)&&grid[now_x][ny]!='#'&&!vis[now_x][ny][1])
            {
                vis[now_x][ny][1] = true;
                q.push({now_x,ny,1,steps+1});
            }
            int ny2 = now_y - 1;
            if(check(now_x,ny2)&&grid[now_x][ny2]!='#'&&!vis[now_x][ny2][1])
            {
                vis[now_x][ny2][1] = true;
                q.push({now_x,ny2,1,steps+1});
            }
        }
    }
    return -1;//无法到达返回-1
    };
    cout << bfs();
    return 0;
}