Summary

This problem asks for the minimum number of moves to travel from the start to the goal on a grid, alternating between “vertical moves” and “horizontal moves”. It can be solved using Breadth-First Search (BFS) by including the direction of the previous move in the state.

Analysis

Issues with a Naive Approach

In a standard shortest path problem, we typically manage only the “current cell \((r, c)\)” as the state and record whether it has been visited. However, in this problem, the direction in which we can move next (vertical or horizontal) is restricted by whether the previous move was vertical or horizontal.

Therefore, if we only record whether “cell \((r, c)\) has been reached”, - “Routes that reached the cell via a vertical move (can only move horizontally next)” - “Routes that reached the cell via a horizontal move (can only move vertically next)”

will be conflated. For instance, even if a route reaches a cell first with the same number of moves, if that route’s incoming direction prevents it from reaching the goal, a later route arriving from a different direction would not be explored, leading to a Wrong Answer (WA).

State Expansion

This issue can be resolved through “state expansion,” which increases the number of vertices (states) in the graph. We represent the robot’s state as the following triplet:

• \((r, c, \text{dir})\)
  • \(r, c\): Current cell (row index, column index)
  • \(\text{dir} = 0\): The previous move was a “vertical move” (can only make a “horizontal move” next)
  • \(\text{dir} = 1\): The previous move was a “horizontal move” (can only make a “vertical move” next)

By separating the states in this way, we can distinguish whether a cell was entered vertically or horizontally and properly track the shortest number of moves for each case.

Algorithm

Since all move costs are \(1\), we can find the minimum number of moves using Breadth-First Search (BFS).

1. Initialization:
   • Initialize the distance array dist[r][c][dir] with \(-1\).
   • Since the very first move from the start \((1, 1)\) can be either vertical or horizontal:
     • If we can move \(1\) cell up or down, set dist[nr][nc][0] = 1 for that cell and push it to the queue.
     • If we can move \(1\) cell left or right, set dist[nr][nc][1] = 1 for that cell and push it to the queue.
2. BFS Transitions:
   • Pop a state \((r, c, \text{dir})\) from the queue.
   • If the popped cell is the goal \((H, W)\), the current number of moves is the minimum (by the properties of BFS, the shortest path is guaranteed when it is first popped).
   • If \(\text{dir} = 0\) (the next move must be horizontal):
     • Check the horizontally adjacent cells \((r, c \pm 1)\) that are within the grid and have no obstacles.
     • If unvisited (dist[r][nc][1] == -1), update the distance and push state \((r, nc, 1)\) to the queue.
   • If \(\text{dir} = 1\) (the next move must be vertical):
     • Check the vertically adjacent cells \((r \pm 1, c)\) that are within the grid and have no obstacles.
     • If unvisited (dist[nr][c][0] == -1), update the distance and push state \((nr, c, 0)\) to the queue.
3. Termination:
   • If the goal is not reached by the time the queue becomes empty, it is unreachable, so output NONE.

Complexity

• Time Complexity: \(O(HW)\)
  • The number of states is \(H \times W \times 2\). From each state, there are at most \(2\) move candidates (up/down for vertical, left/right for horizontal), so the total number of edges traversed is at most \(4HW\). Given \(H, W \le 1000\), the number of states is at most around \(2 \times 10^6\), which easily runs well within the time limit.
• Space Complexity: \(O(HW)\)
  • Storing the grid information \(A\), the distance array dist, and the BFS queue requires \(O(HW)\) memory.

Implementation Notes

• Handling the First Move: Instead of pushing the starting cell \((1, 1)\) itself into the queue as a “special directionless state”, pushing the adjacent cells reachable on the first move with distance \(1\) into the queue beforehand allows the transitions inside the BFS loop to be cleanly unified into the simple alternation: “vertical to horizontal, horizontal to vertical”.

• Using 0-indexing: Representing the grid coordinates using 0-indexing (from \(0\) to \(H-1\) and \(0\) to \(W-1\)) makes boundary checks and array accesses much cleaner and simpler in the code.

  Source Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    vector<vector<int>> A(H, vector<int>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
        }
    }

    // dist[r][c][dir]
    // dir = 0: 直前に縦移動した（次は横移動）
    // dir = 1: 直前に横移動した（次は縦移動）
    vector<vector<vector<int>>> dist(H, vector<vector<int>>(W, vector<int>(2, -1)));
    queue<pair<pair<int, int>, int>> q;

    // 縦方向の初手 (上または下)
    int dr[] = {-1, 1};
    for (int d = 0; d < 2; ++d) {
        int nr = 0 + dr[d];
        int nc = 0;
        if (nr >= 0 && nr < H && A[nr][nc] == 0) {
            dist[nr][nc][0] = 1;
            q.push({{nr, nc}, 0});
        }
    }

    // 横方向の初手 (左または右)
    int dc[] = {-1, 1};
    for (int d = 0; d < 2; ++d) {
        int nr = 0;
        int nc = 0 + dc[d];
        if (nc >= 0 && nc < W && A[nr][nc] == 0) {
            dist[nr][nc][1] = 1;
            q.push({{nr, nc}, 1});
        }
    }

    int ans = -1;

    while (!q.empty()) {
        auto [pos, dir] = q.front();
        q.pop();
        auto [r, c] = pos;

        if (r == H - 1 && c == W - 1) {
            ans = dist[r][c][dir];
            break;
        }

        int d = dist[r][c][dir];

        if (dir == 0) {
            // 次は横移動
            for (int i = 0; i < 2; ++i) {
                int nr = r;
                int nc = c + dc[i];
                if (nc >= 0 && nc < W && A[nr][nc] == 0) {
                    if (dist[nr][nc][1] == -1) {
                        dist[nr][nc][1] = d + 1;
                        q.push({{nr, nc}, 1});
                    }
                }
            }
        } else {
            // 次は縦移動
            for (int i = 0; i < 2; ++i) {
                int nr = r + dr[i];
                int nc = c;
                if (nr >= 0 && nr < H && A[nr][nc] == 0) {
                    if (dist[nr][nc][0] == -1) {
                        dist[nr][nc][0] = d + 1;
                        q.push({{nr, nc}, 0});
                    }
                }
            }
        }
    }

    if (ans != -1) {
        cout << ans << "\n";
    } else {
        cout << "NONE\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.