結果

問題 No.2708 Jewel holder
ユーザー rinrion
提出日時 2024-03-31 17:59:49
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 10
権限があれば一括ダウンロードができます

ソースコード

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