まず、重要な事実として \((1,1)\) から \((3,N)\) までの最短経路では \((x,y)\) から \((x,y-1)\) へ “逆戻り” するようなタイミングが存在しません。したがって、 \(d_{i,j}\) を「マス \((1,1)\) からマス \((i,j)\) へ逆戻りせずに移動する際の最短距離」とすると、求める答えは \(d_{3,N}\) と一致します。

さらに、 \(d_{*,j}\) は \(d_{*,j-1}\) とマス \(S_{*,j}\) の情報のみから決まります。ここで、 \(S_{*,j}\) を \(d_{*,j}\) から \(d_{*,j-1}\) を決める写像であると捉えると、これらの写像はモノイドとなります。したがって、 \(S_{*,j}\) を載せたセグメント木を持ち、一点更新と全体積取得を行うことで答えを求めることができます。

以上を適切に実装することで答えを求めることができます。計算量は \(O(N+Q\log N)\) です。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (n); i++)
template <typename T> bool chmin(T &x, T y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
using SS = array<int, 3>;
using S = array<SS, 3>;
array<S, 9> e8;
S op(S x, S y) {
	S res = e8[7];
	rep(i, 3) rep(j, 3) rep(k, 3) chmin(res[i][j], x[k][j] + y[i][k]);
	return res;
}
S e() { return e8[8]; }
constexpr int INF = 1e9;
int main() {
	e8[0] = S{SS{0, 1, 2}, SS{1, 0, 1}, SS{2, 1, 0}};
	e8[1] = S{SS{INF, INF, INF}, SS{INF, 0, 1}, SS{INF, 1, 0}};
	e8[2] = S{SS{0, INF, INF}, SS{INF, INF, INF}, SS{INF, INF, 0}};
	e8[3] = S{SS{INF, INF, INF}, SS{INF, INF, INF}, SS{INF, INF, 0}};
	e8[4] = S{SS{0, 1, INF}, SS{1, 0, INF}, SS{INF, INF, INF}};
	e8[5] = S{SS{INF, INF, INF}, SS{INF, 0, INF}, SS{INF, INF, INF}};
	e8[6] = S{SS{0, INF, INF}, SS{INF, INF, INF}, SS{INF, INF, INF}};
	e8[7] = S{SS{INF, INF, INF}, SS{INF, INF, INF}, SS{INF, INF, INF}};
	e8[8] = S{SS{0, INF, INF}, SS{INF, 0, INF}, SS{INF, INF, 0}};
	int n;
	cin >> n;
	vector<int> s(n);
	rep(j, 3) {
		string ss;
		cin >> ss;
		rep(i, n) if (ss[i] == '#') s[i] |= 1 << j;
	}
	vector<S> to_seg(n);
	rep(i, n) to_seg[i] = e8[s[i]];
	atcoder::segtree<S, op, e> seg(to_seg);
	int que;
	cin >> que;
	while (que--) {
		int r, c;
		cin >> r >> c;
		r--, c--;
		s[c] ^= 1 << r;
		seg.set(c, e8[s[c]]);
		auto res = seg.all_prod();
		cout << (res[2][0] == INF ? -1 : n - 1 + res[2][0]) << '\n';
	}
}