読者です 読者をやめる 読者になる 読者になる

誤読

文字通りくそコード

ARC044-C ビーム

マンハッタン距離は分解して解くことが多い

DPー>(H+W)*Tで思考停止しない

変化がどれだけあるかわかってるなら余計なところを削れるかも

signed main() {
	int w[2], q;
	scanf("%d %d %d", &w[0], &w[1], &q);
 
	map<int,set<int>> biim[2];
 
	REP(i, q) {
		itn a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		c--;
		biim[b][a].insert(c);
	}
	int ans = 0;
 
	REP(cc, 2) {
		int dp[100001] = {};
 
		set<int> bef;
		for (auto itr : biim[cc]) {
			for (auto itr2 = bef.begin(); itr2 != bef.end(); itr2++) {
				if (*itr2 > 0) dp[*itr2] = dp[*itr2 - 1] + 1;
				if (*itr2 < w[cc] - 1) dp[*itr2] = min(dp[*itr2], dp[*itr2 + 1] + 1);
			}
			for (auto itr2 = bef.rbegin(); itr2 != bef.rend(); itr2++) {
				if (*itr2 > 0) dp[*itr2] = dp[*itr2 - 1] + 1;
				if (*itr2 < w[cc] - 1) dp[*itr2] = min(dp[*itr2], dp[*itr2 + 1] + 1);
			}
			for (auto itr2 : itr.second) {
				dp[itr2] = INT_MAX-100000;
			}
			bef = itr.second;
		}
		int ad = INT_MAX;
		REP(i, w[cc]) {
			ad = min(ad, dp[i]);
		}
		if (ad >= INT_MAX-100000) {
			printf("-1\n");
			return 0;
		}
		ans += ad;
	}
	printf("%d\n", ans);
	return 0;
}