Submission #11046860

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;

/**
 * Contest : AtCoder Grand Contest 043
 * Contest URL : https://atcoder.jp/contests/agc043
 * Problem : 
 * Problem URL : 
 */

void solve() {
	int H, W;
	cin >> H >> W;
	vector < string > matrix (H);
	for (int i = 0; i < H; i++) {
		cin >> matrix[i];
	}
	vector < vector < int > > dp (H, vector < int > (W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (i == 0 && j == 0) {
				dp[i][j] = (matrix[i][j] == '#');
			} else if (i == 0) {
				dp[i][j] = dp[i][j - 1] + (matrix[i][j] == '#');
			} else if (j == 0) {
				dp[i][j] = dp[i - 1][j] + (matrix[i][j] == '#');
			} else {
				dp[i][j] = min (dp[i - 1][j], dp[i][j - 1]) + (matrix[i][j] == '#');
			}
		}
	}
	cout << dp[H - 1][W - 1] << endl;
}

int main() {
	int T = 1;
	//scanf ("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Submission Info

Judge Result