結果

問題 No.2708 Jewel holder
ユーザー rinrionrinrion
提出日時 2024-03-31 17:59:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,589 bytes
コンパイル時間 4,818 ms
コンパイル使用メモリ 231,288 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-09-30 21:13:14
合計ジャッジ時間 4,116 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 1 ms
6,816 KB
testcase_07 WA -
testcase_08 AC 2 ms
6,816 KB
testcase_09 WA -
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 1 ms
6,820 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 1 ms
6,816 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;

#define rep(i, s, n) for(int i = s; i < (int)(n); i++)
#define repr(i, s, n) for(int i = ((int)(n) - 1); i >= s; i--)

int h, w, hw;
vector<int> di2 = {0, 1}, dj2 = {1, 0}; 
vector<int> seen;
vector<char> a;

#define ij_no(i, j) ((int) (i) * w + (int) (j)) // マス目の座標→通し番号
#define no_i(no) ((int) no / w)  // 通し番号→ 座標i
#define no_j(no) ((int) no % w) // 通し番号→ 座標j
#define move2_i(i, d) ((int) i + di2[d]) // 2方向の移動後i座標
#define move2_j(j, d) ((int) j + dj2[d]) // 2方向の移動後j座標

bool frame_in(int ni, int nj, int h, int w){
	if(0 <= ni && ni < h && 0 <= nj && nj < w) return true;
	else return false;
}

int move2_no(int no, int dir, int h, int w){ // 2方向の移動後no 枠外なら -1を返す
	int nxi = move2_i(no_i(no), dir), nxj = move2_j(no_j(no), dir);
	if(!frame_in(nxi, nxj, h, w)){
		return -1;
	}
	else return ij_no(nxi, nxj);
}

void dfs(int v, int &ans, int &now){
	if(v == hw - 1){
		ans ++;
		return;
	}
	if(seen[v]) return;
	seen[v] = 1;

	if(a[v] == 'o') now ++;
	else if(a[v] == 'x') now --;
	if(now < 0) return ;

	rep(i, 0, 2){
		int nx = move2_no(v, i, h, w);
		if(nx != -1 && a[nx] != '#') dfs(nx, ans, now);
	}
	
	seen[v] = 0;
	if(a[v] == 'o') now --;
	else if(a[v] == 'x') now ++;
}

int main(){
	cin >> h >> w;
	hw = h * w;
	a.resize(hw);
	seen.assign(hw, 0);

	rep(i, 0, hw) cin >> a[i];
	
	int ans = 0;
	int now = 0;
	dfs(0, ans, now);
	
	cout << ans << endl;
	
}
0