提出 #11046913

ソースコード 拡げる

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
#define MRE assert(0);
const int inf = 1e17;
const int mod = 998244353;
typedef pair<int, int> P;
typedef pair<int, P> PP;
string s[105];
int dp[105][105];
int dx[] = { 0,1 }, dy[] = { 1,0 };
signed main() {
	int h, w; cin >> h >> w;
	rep(i, h)cin >> s[i];
	rep(i, h)rep(j, w)dp[i][j] = inf;
	priority_queue<PP>Q;
	if (s[0][0] == '.') {
		Q.push(PP(0, P(0, 0)));
		dp[0][0] = 0;
	}
	else {
		Q.push(PP(1, P(0, 0)));
		dp[0][0] = 1;
	}
	while (Q.size()) {
		PP p = Q.top(); Q.pop();
		int d = p.first, ni = p.second.first, nj = p.second.second;
		if (d > dp[ni][nj])continue;
		rep(j, 2) {
			int mi = ni + dx[j], mj = nj + dy[j];
			if (0 <= mi&&mi < h && 0 <= mj&&mj < w) {
				int nd;
				if (s[ni][nj] == '.'&&s[mi][mj] == '#')nd = d + 1;
				else nd = d;
				if (nd < dp[mi][mj]) {
					dp[mi][mj] = nd;
					Q.push(PP(nd, P(mi, mj)));
				}
			}
		}
	}
	cout << dp[h - 1][w - 1] << endl;
}

提出情報

提出日時
問題 A - Range Flip Find Route
ユーザ Rho17
言語 C++14 (GCC 5.4.1)
得点 400
コード長 1043 Byte
結果 AC
実行時間 18 ms
メモリ 384 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 4
AC × 17
セット名 テストケース
Sample example_00, example_01, example_02, example_03
All corner_00, corner_01, example_00, example_01, example_02, example_03, kuronuri_00, max_answer_00, max_answer_01, max_answer_02, max_random_00, max_random_01, max_random_02, max_random_03, one_path_00, one_path_01, one_path_02
ケース名 結果 実行時間 メモリ
corner_00 AC 2 ms 384 KiB
corner_01 AC 2 ms 384 KiB
example_00 AC 1 ms 256 KiB
example_01 AC 1 ms 256 KiB
example_02 AC 1 ms 256 KiB
example_03 AC 1 ms 256 KiB
kuronuri_00 AC 2 ms 384 KiB
max_answer_00 AC 3 ms 384 KiB
max_answer_01 AC 3 ms 384 KiB
max_answer_02 AC 3 ms 384 KiB
max_random_00 AC 15 ms 384 KiB
max_random_01 AC 16 ms 384 KiB
max_random_02 AC 16 ms 384 KiB
max_random_03 AC 13 ms 384 KiB
one_path_00 AC 18 ms 384 KiB
one_path_01 AC 18 ms 384 KiB
one_path_02 AC 17 ms 384 KiB