結果

問題 No.2708 Jewel holder
ユーザー anago-pie
提出日時 2024-04-09 15:21:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,677 bytes
コンパイル時間 2,454 ms
コンパイル使用メモリ 210,428 KB
最終ジャッジ日時 2025-02-20 23:22:15
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0