#970854 (C++17) No.2708 Jewel holder

• 問題: No.2708 Jewel holder
• ユーザー: anago-pie
• 提出日時: 2024-04-09 15:21:44
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 1,677 bytes
• コンパイル時間: 2,770 ms
• コンパイル使用メモリ: 218,388 KB
• 実行使用メモリ: 6,824 KB
• 最終ジャッジ日時: 2024-10-01 17:50:52
• 合計ジャッジ時間: 3,324 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,820 KB
testcase_03	AC	2 ms; 6,816 KB
testcase_04	AC	2 ms; 6,820 KB
testcase_05	AC	2 ms; 6,820 KB
testcase_06	AC	2 ms; 6,816 KB
testcase_07	AC	2 ms; 6,820 KB
testcase_08	AC	2 ms; 6,820 KB
testcase_09	AC	2 ms; 6,820 KB
testcase_10	AC	2 ms; 6,824 KB
testcase_11	AC	2 ms; 6,816 KB
testcase_12	AC	2 ms; 6,816 KB
testcase_13	AC	2 ms; 6,816 KB
testcase_14	AC	2 ms; 6,820 KB
testcase_15	AC	2 ms; 6,820 KB
testcase_16	AC	2 ms; 6,820 KB
testcase_17	AC	2 ms; 6,820 KB
testcase_18	AC	2 ms; 6,816 KB
testcase_19	AC	2 ms; 6,820 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define debug 0
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
using ll = long long;
using ld = long double;
const int mod = 998244353;
const int MOD = 1000000007;
const double pi = atan2(0, -1);
#include <time.h>
#include <chrono>

int main() {
	int H, W;
	cin >> H >> W;
	vector<string> grid(H);
	rep(i, H) {
		cin >> grid[i];
	}

	vector<vector<vector<int>>> dp(H, vector<vector<int>>(W, vector<int>(105, 0)));
	dp[0][0][1] = 1;
	set<vector<int>> s;
	s.insert({ 0,0,0 });
	while (!s.empty()) {
		vector<int> v = *begin(s);
		vector<int> now = { v[1], v[2] };

		s.erase(v);
		if (grid[now[0]][now[1]] == '#') {
			continue;
		}
		if (now[0] < H - 1 && grid[now[0] + 1][now[1]] == 'o') {
			rep(i, 101) {
				dp[now[0] + 1][now[1]][i + 1] += dp[now[0]][now[1]][i];
			}
			s.insert({ now[0] + now[1] + 1, now[0] + 1, now[1] });
		}
		else if (now[0] < H - 1 && grid[now[0] + 1][now[1]] == 'x') {
			for (int i = 1; i <= 100; i++) {
				dp[now[0] + 1][now[1]][i - 1] += dp[now[0]][now[1]][i];
			}
			s.insert({ now[0] + now[1] + 1, now[0] + 1, now[1] });
		}

		if (now[1] < W - 1 && grid[now[0]][now[1]+1] == 'o') {
			rep(i, 101) {
				dp[now[0]][now[1]+1][i + 1] += dp[now[0]][now[1]][i];
			}
			s.insert({ now[0] + now[1] + 1, now[0], now[1]+1 });
		}
		else if (now[1] < W - 1 && grid[now[0]][now[1]+1] == 'x') {
			for (int i = 1; i <= 100; i++) {
				dp[now[0]][now[1]+1][i - 1] += dp[now[0]][now[1]][i];
			}
			s.insert({ now[0] + now[1] + 1, now[0], now[1]+1 });
		}
	}

	int ans = 0;
	rep(i, 101) {
		ans += dp[H - 1][W - 1][i];
	}
	cout << ans << endl;
}