โจทย์ข้อนี้เป็นโจทย์หาเส้นทางบน Implicit Graph ซึ่งนิยามดังนี้

กำหนดให้มี node $(x, y)$ สำหรับทุก $x=0,1,2,\dots,t$ และ $y=0,1,2,\dots,m$ ที่ ณ เวลาวินาทีที่ $x$ เลนที่ $y$ ไม่มีสิ่งกีดขวางอยู่ (ณ เวลา $x=0$ ไม่มีสิ่งกีดขวางเสมอ)

กำหนดให้มีเส้นเชื่อม

1. $(x,y) \to (x+1,y-1)$
2. $(x,y) \to (x+1,y+1)$
3. $(x,y) \to (x+1,y)$

แทนการขับรถที่เป็นไปได้ในแต่ละกรณี (จะมีเส้นเชื่อมก็ต่อเมื่อทั้ง node ต้นทางและปลายทางมีอยู่จริง)

เราสามารถใช้ Breadth-first Search หรือ Dijkstra's Algorithm หาเส้นทางสั้นสุดจาก $(0,n)$ ไป $(t,y)$ สำหรับ $y$ ใด ๆ (หาเส้นทางสั้นสุดจากเวลาวินาทีที่ $0$ เลนเริ่มต้นที่ $n$ ไปยังเวลา $t$ เลนใดก็ได้) พร้อมเก็บ parent เพื่อที่สามารถแสดงผลเส้นทางคำตอบได้

อนึ่ง สามารถใช้ Depth-first Search ได้ด้วยเนื่องจากเป็น directed graph และเส้นทางสั้นสุดความยาวเท่ากับ $m$ เสมอ แต่เนื่องจากเส้นทางเดินจาก $(0,n)$ ไปยัง node อื่น ๆ อาจมีจำนวนเป็น exponential ดังนั้น ระหว่างการทำ Depth-first Search ควรบันทึกด้วยว่าเคยไป node ไหนแล้วไม่ประสบความสำเร็จในการเดินทางไป $(t,y)$ เพื่อลดเวลาการทำงานของโปรแกรม

Time Complexity: $O(tm)$ เมื่อใช้ Breadth-first search หรือ Depth-first search

Space Complexity: $O(tm)$

Implementation

ในภาษา C++:

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int dy[] = {0, -1, 1, 0};  // -, left, right, middle
int rdy[] = {0, 1, -1, 0}; // reversed
int m, n, t;
int A[110][50], dist[110][50];
int par[110][50];

int main() {
  scanf("%d%d%d", &m, &n, &t);
  for (int x = 1; x <= t; ++x) {
    for (int y = 1; y <= m; ++y)
      scanf("%d", &A[x][y]);
  }

  queue<pii> Q;
  Q.push(pii(0, n));
  int ax, ay;
  while (!Q.empty()) {
    int x = Q.front().first;
    int y = Q.front().second;
    Q.pop();
    if (x == t) {
      ax = x;
      ay = y;
      break;
    }
    for (int i = 1; i <= 3; ++i) {
      int ny = y + dy[i];
      if (ny >= 1 && ny <= m && !A[x + 1][ny] && !par[x + 1][ny]) {
        par[x + 1][ny] = i;
        dist[x + 1][ny] = dist[x][y] + 1;
        Q.push(pii(x + 1, ny));
      }
    }
  }

  stack<int> ans;
  while (ax != 0) {
    ans.push(par[ax][ay]);
    ay = ay + rdy[par[ax][ay]];
    ax = ax - 1;
  }
  while (!ans.empty()) {
    printf("%d\n", ans.top());
    ans.pop();
  }

  return 0;
}