結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー kaffelun
提出日時 2018-04-10 13:01:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,563 bytes
コンパイル時間 2,271 ms
コンパイル使用メモリ 167,284 KB
実行使用メモリ 52,736 KB
最終ジャッジ日時 2024-06-26 20:54:14
合計ジャッジ時間 15,086 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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