考察

各階の連結成分をそれぞれ \(1\) 個の頂点として，隣り合う階のあいだで触れている頂点のあいだに辺を張ったグラフを考えます．

以下を階番号が高いほうから求めます．

• \(dp_0[f][v]\): \(f\) 階の頂点 \(v\) を始点として，\(f+1\) 階よりも下の階でハシゴを使う場合の，コイン回収枚数の最大値
• \(dp_1[f][v]\): \(f\) 階の頂点 \(v\) を始点として，ハシゴを使わない場合の，コイン回収枚数の最大値
• \(dv_0[f][v][u]\): \(f\) 階の頂点 \(v\) を始点として，ハシゴを使わず，\(v\) から \(f+1\) 階の頂点 \(u\) に上る場合の，コイン回収枚数の最大値
• \(dv_1[f+1][u][v]\): \(f+1\) 階の頂点 \(u\) を始点として，\(u\) からハシゴを使って \(f\) 階の頂点 \(v\) に下る場合の，コイン回収枚数の最大値

頂点 \(v\) にあるコインの総数を \(c_v\) とします．

\(dp_0[f][v]\), \(dv_0[f][v][u]\) については，隣接する \(f+1\) 階の各頂点 \(u\) に対する \(dp_0[f+1][u], dp_1[f+1][u]\) を見ることで求まります．

\(dv_0[f][v][w]\) から \(dv_1[f+1][u][v]\) を求めるには，\(v\) に隣接する各 \(w\) に対する以下の値の最大値をとります．

• \(u = w\) の場合，\(dv_0[f][v][w]\)．
• \(u \neq w\) の場合，\(dv_0[f][v][w] + c_u\)．

ここで，\(u \neq w\) に対する \(dv_0[f][v][w]\) の最大値は，\(dv_0[f][v][w]\) 全体において上から \(2\) 位以内に存在します．よって，あらかじめ \(dv_0[f][v][w]\) の全体上位 \(2\) 値を求め，遷移においてはその \(2\) 値のみを見れば十分です．

同様にして，\(dv_1[f+1][u][v]\) および \(dp_1[f+1][u]\) から \(dp_1[v]\) を求めることができます．

実装例 (C++)

#include <iostream>
using std::cin;
using std::cout;
#include <vector>
using std::vector;
using std::pair;
#include <algorithm>
using std::sort;
using std::min;
using std::max;
#include <string>
using std::string;
#include <set>
using std::set;

#include <atcoder/dsu>
using atcoder::dsu;

typedef long long int ll;
typedef pair<ll, ll> P;

const ll MOD = 998244353;

ll f, h, w;
vector<vector<string> > s;
vector<vector<vector<ll> > > vs;
ll q;
vector<ll> g, x, y;

void chmax (ll &l, ll r) {
	if (l < r) l = r;
}
void chmin (ll &l, ll r) {
	if (l > r) l = r;
}

void solve () {
	vs.resize(f);
	for (ll k = 0; k < f; k++) {
		vs[k].resize(h);
		for (ll i = 0; i < h; i++) {
			vs[k][i].resize(w);
			for (ll j = 0; j < w; j++) {
				if (s[k][i][j] == '#') {
					vs[k][i][j] = -1;
				} else {
					vs[k][i][j] = (s[k][i][j] - '0');
				}
			}
		}
	}

	vector<dsu> ds;
	for (ll k = 0; k < f; k++) {
		dsu d(h*w);
		for (ll i = 0; i < h; i++) {
			for (ll j = 0; j < w; j++) {
				if (vs[k][i][j] == -1) continue;

				if (i-1 >= 0 && vs[k][i-1][j] != -1) {
					d.merge((i-1)*w+j, i*w+j);
				}
				if (j-1 >= 0 && vs[k][i][j-1] != -1) {
					d.merge(i*w+(j-1), i*w+j);
				}
			}
		}
		ds.push_back(d);
	}

	vector<ll> isroot[f];
	// vx[k][root]: sum of component[k][root]
	vector<ll> vx[f];
	// vgu[k][root]: edge [k]->[k+1], component-wise (unique)
	// vgd[k][root]: edge [k]->[k-1], component-wise (unique)
	vector<ll> vgu[f][h*w], vgd[f][h*w];
	for (ll k = 0; k < f; k++) {
		isroot[k].assign(h*w, 0);
		vx[k].assign(h*w, 0);

		vector<set<ll> > tu(h*w), td(h*w);
		for (ll i = 0; i < h; i++) {
			for (ll j = 0; j < w; j++) {
				if (vs[k][i][j] != -1) {
					ll idx = ds[k].leader(i*w+j);
					isroot[k][idx] = 1;
					vx[k][idx] += vs[k][i][j];

					if (k-1 >= 0 && vs[k-1][i][j] != -1) {
						ll jdx = ds[k-1].leader(i*w+j);
						td[idx].insert(jdx);
					}
					if (k+1 <  f && vs[k+1][i][j] != -1) {
						ll jdx = ds[k+1].leader(i*w+j);
						tu[idx].insert(jdx);
					}
				}
			}
		}

		for (ll i = 0; i < h*w; i++) {
			for (ll v : td[i]) vgd[k][i].push_back(v);
			for (ll v : tu[i]) vgu[k][i].push_back(v);
		}
	}

	ll dp0[f][h*w], dp1[f][h*w];
	ll up1[f][h*w];
	vector<P> dv0[f][h*w], dv1[f][h*w];
	for (ll k = f-1; k >= 0; k--) {
		for (ll v = 0; v < h*w; v++) {
			dp0[k][v] = 0;
			dp1[k][v] = 0;
			up1[k][v] = 0;

			dv0[k][v].clear();
			dv1[k][v].clear();
		}

		// simple
		for (ll v = 0; v < h*w; v++) {
			if (!isroot[k][v]) continue;

			ll origin = vx[k][v];
			ll drop0 = 0;
			ll drop1 = 0;
			if (k+1 < f) {
				for (ll u : vgu[k][v]) {
					chmax(drop0, dp0[k+1][u]);
					chmax(drop1, dp1[k+1][u]);
				}
			}

			dp0[k][v] = origin + drop0;
			dp1[k][v] = origin + drop1;
		}
		// simple end

		// zigzag
		if (k+1 < f) {
			// [k][0]->[k+1][0]
			for (ll v = 0; v < h*w; v++) {
				if (!isroot[k][v]) continue;

				ll curr = vx[k][v];
				for (ll u : vgu[k][v]) {
					ll sum = curr + dp0[k+1][u];
					dv0[k][v].push_back({sum, u});
				}
				sort(   dv0[k][v].begin(), dv0[k][v].end()); // LOG
				reverse(dv0[k][v].begin(), dv0[k][v].end());
			}
			// [k+1][1]->[k][0]
			for (ll v = 0; v < h*w; v++) {
				if (!isroot[k+1][v]) continue;

				ll curr = vx[k+1][v];
				for (ll u : vgd[k+1][v]) {
					ll sum = 0;
					for (ll ui = 0; ui < min(2LL, (ll)dv0[k][u].size()); ui++) {
						ll add = dv0[k][u][ui].first;
						ll idx = dv0[k][u][ui].second;
						if (idx == v) {
							chmax(sum, add);
						} else {
							chmax(sum, curr + add);
						}
					}
					chmax(up1[k+1][v], sum);
					dv1[k+1][v].push_back({sum, u});
				}
				sort(   dv1[k+1][v].begin(), dv1[k+1][v].end()); // LOG
				reverse(dv1[k+1][v].begin(), dv1[k+1][v].end());
			}
			// [k][1]->[k+1][1]
			for (ll v = 0; v < h*w; v++) {
				if (!isroot[k][v]) continue;

				ll curr = vx[k][v];
				for (ll u : vgu[k][v]) {
					ll sum = 0;
					for (ll ui = 0; ui < min(2LL, (ll)dv1[k+1][u].size()); ui++) {
						ll add = dv1[k+1][u][ui].first;
						ll idx = dv1[k+1][u][ui].second;
						if (idx == v) {
							chmax(sum, add);
						} else {
							chmax(sum, curr + add);
						}
					}
					
					chmax(dp1[k][v], sum);
				}
			}
		}
		// zigzag end
	}

	for (ll qi = 0; qi < q; qi++) {
		ll ans = 0;
		ll idx = ds[g[qi]].leader(x[qi] * w + y[qi]);
		chmax(ans, dp0[g[qi]][idx]);
		chmax(ans, dp1[g[qi]][idx]);
		chmax(ans, up1[g[qi]][idx]);

		cout << ans << "\n";
	}

	return;
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> f >> h >> w;
	s.resize(f);
	for (ll k = 0; k < f; k++) {
		s[k].resize(h);
		for (ll i = 0; i < h; i++) {
			cin >> s[k][i];
		}
	}

	cin >> q;
	g.resize(q);
	x.resize(q);
	y.resize(q);
	for (ll i = 0; i < q; i++) {
		cin >> g[i] >> x[i] >> y[i];
		g[i]--;
		x[i]--;
		y[i]--;
	}

	solve();

	
	return 0;
}