結果

問題 No.34 砂漠の行商人
ユーザー kaffelunkaffelun
提出日時 2018-04-10 13:01:17
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,563 bytes
コンパイル時間 1,566 ms
コンパイル使用メモリ 155,076 KB
実行使用メモリ 45,296 KB
最終ジャッジ日時 2023-09-09 03:46:10
合計ジャッジ時間 15,400 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
11,484 KB
testcase_01 AC 3 ms
4,480 KB
testcase_02 AC 9 ms
4,996 KB
testcase_03 AC 24 ms
6,004 KB
testcase_04 AC 2,355 ms
18,160 KB
testcase_05 AC 529 ms
15,012 KB
testcase_06 AC 32 ms
6,732 KB
testcase_07 AC 1,374 ms
22,680 KB
testcase_08 AC 2,726 ms
31,256 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int N, V, Sx, Sy, Gx, Gy;
int m[100][100];
map<int, int> ans_p[100][100];
map<int, int> ans_v[100][100];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

bool range_check(int y, int x, int h, int w = -1) {
    if(w < 0) w = h;
    return (0 <= x && x < w && 0 <= y && y < h);
}
template<typename KeyType, typename ValueType> 
std::pair<KeyType,ValueType> get_min( const std::map<KeyType,ValueType>& x ) {
  using pairtype=std::pair<KeyType,ValueType>; 
  return *std::min_element(x.begin(), x.end(), [] (const pairtype & p1, const pairtype & p2) {
        return p1.second < p2.second;
  }); 
}

void recursive(int y, int x, int v, int p) {
	// 死亡または不要な解
	if(v <= 0) return;
	if (ans_p[y][x].count(v) > 0 && ans_p[y][x][v] <= p) return;
	if (ans_v[y][x].count(p) > 0 && ans_v[y][x][p] >= v) return;
	ans_p[y][x][v] = p;
	ans_v[y][x][p] = v;
	for(int d = 0; d < 4; d++) {
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		if(!range_check(ny, nx, N)) continue;
		recursive(ny, nx, v - m[ny][nx], p + 1);
	}
}

int main() {
	#ifdef DEBUG
	std::ifstream in("/home/yusuke/inputf.in");
	std::cin.rdbuf(in.rdbuf());
	#endif
	
	cin >> N >> V >> Sx >> Sy >> Gx >> Gy;
	Sx--, Sy--, Gx--, Gy--;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> m[i][j];
			ans_p[i][j] = map<int, int>();
			ans_v[i][j] = map<int, int>();
		}
	}
	recursive(Sy, Sx, V, 0);
	if (ans_p[Gy][Gx].empty()) {
		cout << -1 << endl;
	} else {
		cout << get_min(ans_p[Gy][Gx]).second << endl;
	}
	return 0;
}
0