As an important fact, when we travel from \((1,1)\) to \((3,N)\) on a shortest path, we never “step back” from \((x,y)\) to \((x,y-1)\). Thus, if we define \(d_{i,j}\) as the shortest distance from cell \((1,1)\) to \((3,N)\) without stepping back, the sought answer coincides with \(d_{3,N}\).

Moreover, \(d_{i,*}\) is solely determined by \(d_{i-1,*}\) and \(S_{i,*}\). If we regard \(S_{i,*}\) as a mapping that takes \(d_{i-1,*}\) and returns \(d_{i,*}\), these maps form a monoid. Therefore, we can maintain a segment tree storing \(S_{i,*}\), and perform element-wise updates and global-product retrievals.

The answers can be found by appropriately implementing these ideas. The computational complexity is \(O(N+Q\log N)\).

Sample code (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';
	}
}