#967853 (C++14) No.2708 Jewel holder

• 問題: No.2708 Jewel holder
• ユーザー: rinrion
• 提出日時: 2024-03-31 17:59:49
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,589 bytes
• コンパイル時間: 4,047 ms
• コンパイル使用メモリ: 231,456 KB
• 実行使用メモリ: 6,676 KB
• 最終ジャッジ日時: 2024-03-31 17:59:54
• 合計ジャッジ時間: 4,656 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

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

ソースコード

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