交互移動の制約がなければ、よく知られている通り

\(\mathrm{dist}[i][j]=(i,j) に到達するための最小移動回数\)

とする BFS により解くことができます。

この問題も同様に、「直前の移動が縦移動・横移動のどちらであったか」の情報を持ち

\(\mathrm{dist}[i][j][k]= 直前の移動が(k?縦移動:横移動)で (i,j) に到達するための最小移動回数\)

とする BFS により解くことができます。計算量は \(O(HW)\) です。

実装例 (C++)

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

int main(){
  int h, w;
  cin >> h >> w;
  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];

  int INF = 1e9;
  vector<vector<vector<int>>> dist(h, vector<vector<int>>(w, vector<int>(2, INF)));

  queue<array<int,3>> q({{0,0,0}, {0,0,1}});
  dist[0][0][0] = 0;
  dist[0][0][1] = 0;

  while(q.size() > 0){
    auto [i, j, k] = q.front(); q.pop();
    vector<pair<int,int>> d;
    if(k == 0){
      d = {{1,0}, {-1,0}};
    }else{
      d = {{0,1}, {0,-1}};
    }
    for(auto [di, dj]: d){
      int ii = i + di;
      int jj = j + dj;
      int kk = k ^ 1;
      if(0<=ii&&ii<h && 0<=jj&&jj<w && a[ii][jj]==0 && dist[ii][jj][kk]==INF){
        dist[ii][jj][kk] = dist[i][j][k] + 1;
        q.push({ii, jj, kk});
      }
    }
  }

  int ans = min(dist[h-1][w-1][0], dist[h-1][w-1][1]);
  if(ans == INF){
    cout << "NONE" << endl;
  }else{
    cout << ans << endl;
  }
}

実装例 (Python)

H, W = map(int, input().split())
A = [input().split() for _ in range(H)]

INF = 10**9
dist = [[[INF, INF] for _ in range(W)] for _ in range(H)]

q = [(0,0,0), (0,0,1)]
dist[0][0][0] = 0
dist[0][0][1] = 0

for i, j, k in q:
  if k == 0:
    d = [(1,0), (-1,0)]
  else:
    d = [(0,1), (0,-1)]
  for di, dj in d:
    ii = i + di
    jj = j + dj
    kk = k ^ 1
    if 0<=ii<H and 0<=jj<W and A[ii][jj]=="0" and dist[ii][jj][kk]==INF:
      dist[ii][jj][kk] = dist[i][j][k]+1
      q.append((ii, jj, kk))

ans = min(dist[H-1][W-1])
if ans == INF:
  print("NONE")
else:
  print(ans)