結果
問題 | No.34 砂漠の行商人 |
ユーザー | xoke0114 |
提出日時 | 2019-01-04 11:43:14 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,293 bytes |
コンパイル時間 | 1,797 ms |
コンパイル使用メモリ | 189,164 KB |
実行使用メモリ | 409,120 KB |
最終ジャッジ日時 | 2024-05-03 02:44:47 |
合計ジャッジ時間 | 13,383 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 17 ms
21,504 KB |
testcase_03 | AC | 15 ms
18,304 KB |
testcase_04 | AC | 97 ms
103,936 KB |
testcase_05 | AC | 130 ms
138,240 KB |
testcase_06 | AC | 72 ms
81,408 KB |
testcase_07 | AC | 186 ms
205,056 KB |
testcase_08 | AC | 252 ms
278,656 KB |
testcase_09 | AC | 4,232 ms
234,240 KB |
testcase_10 | TLE | - |
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 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; using ull = unsigned long long; using ll = long long; #define endl "\n" #define REP(i, n) for (ll i = 0; i < n; i++) #define REPR(i, n) for (ll i = n; i >= 0; i--) #define FOR(i, m, n) for (ll i = m; i < n; i++) #define pb push_back #define fill(x, y) memset(x, y, sizeof(x)) #define even(x) (x) % 2 == 0 #define odd(x) (x) % 2 != 0 #define all(x) x.begin(), x.end() #define pcnt __builtin_popcount #define buli(x) __builtin_popcountll(x) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()); #define IN1(type, x) type x; cin >> x; #define inll(x) ll x; cin >> x; #define indo(x) double x; cin >> x; // these functions return the position of result of Binary Search. #define LB(s, t, x) (int) (lower_bound(s, t, x) - s) #define UB(s, t, x) (int) (upper_bound(s, t, x) - s) ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1) ans = 1ll * ans * a % mo; a = 1ll * a * a % mo; } while (b >>= 1); return ans; } ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { ll temp = gcd(a, b); return temp ? (a / temp * b) : 0; } int mDays[] = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; int dx8[] = { 1, -1, 0, 0, 1, 1, -1, -1 }, dy8[] = { 0, 0, -1, 1, -1, 1, -1, 1 }; template<typename F> class #if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) [[nodiscard]] #elif defined(__GNUC__) && __GNUC_PREREQ(3, 4) __attribute__((warn_unused_result)) #endif // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) FixPoint : F { public: explicit constexpr FixPoint(F&& f) noexcept : F(std::forward<F>(f)) {} template<typename... Args> constexpr decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; // class FixPoint template<typename F> static inline constexpr decltype(auto) makeFixPoint(F&& f) noexcept { return FixPoint<F>{std::forward<F>(f)}; } template <typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template <typename T, typename... Ts> auto make_v(size_t a, size_t b, Ts... ts) { return vector<decltype(make_v<T>(b, ts...))>(a, make_v<T>(b, ts...)); } template <typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) { t = v; } template <typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); } // auto dp = make_v<int>(4, h, w); // fill_v(dp, 0); const ll MOD_CONST = (ll)(1e9 + 7); template <typename T> vector<T> pows(int b, int n) { vector<T> ret; T x = 1; while (ret.size() < n) { ret.push_back(x); x *= b; } return ret; } // find string "from" in "str", and replace them to "to" void strReplace(std::string& str, const std::string& from, const std::string& to) { std::string::size_type pos = 0; while (pos = str.find(from, pos), pos != std::string::npos) { str.replace(pos, from.length(), to); pos += to.length(); } } template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } inline tuple<ll, ll> rotate45(tuple<ll, ll> point) { ll x = get<0>(point), y = get<1>(point); return tuple<ll, ll>(x + y, x - y); } inline bool rangeCheck2D(int nx, int ny, int Width, int Height) { return nx >= 0 and nx < Width and ny >= 0 and ny < Height; } template <typename T> vector<T> INPA(ll n) { vector<T> x; REP(i, n) { T tmp; cin >> tmp; x.push_back(tmp); } return move(x); } // base^x % MOD - O(x) ll p_base(ll base, ll x) { ll ans = 1; REP(i, x) { ans *= base; ans %= MOD_CONST; } return ans; } template <typename T> void out(T o) { cout << o << endl; } template <typename T> void out(vector<T> &out) { REP(i, (int)out.size()) { cout << out[i]; if (i == (int)out.size() - 1) cout << endl; else cout << " "; } } template <typename T> void out(vector<vector<T>> o) { REP(i, o.size()) out(o[i]); } void YesNo(bool f) { cout << (f?"Yes":"No") << endl; } void YESNO(bool f) { cout << (f?"YES":"NO") << endl; } // use " for (const auto& e : V) // lambda expression // auto f = [](int arg1, double arg2) { return ret; }; // lambda recursion // auto result = makeFixPoint([&](auto rec, int pos, int v) -> int { // rec(pos, v); // })(0, 1); int main(void) { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20); inll(N); inll(V); inll(sx); sx--; inll(sy); sy--; inll(gx); gx--; inll(gy); gy--; auto fd = make_v<int>(N, N); REP(i, N) REP(j, N) cin >> fd[i][j]; int vnum = 10100; auto dp = make_v<int>(N, N, vnum); fill_v(dp, INT32_MAX); queue<tuple<int, int, int>> q; // y, x, v; q.push(make_tuple(sy, sx, V)); dp[sy][sx][V] = 0; while (q.size()) { int cy, cx, cv; tie(cy, cx, cv) = q.front(); q.pop(); REP(i, 4) { int nx = cx + dx[i]; int ny = cy + dy[i]; if (not rangeCheck2D(nx, ny, N, N)) continue; int nv = cv - fd[ny][nx]; if (nv <= 0) continue; if (chmin(dp[ny][nx][nv], dp[cy][cx][cv] + 1)) q.push(make_tuple(ny, nx, nv)); } } int ans = INT32_MAX; REP(i, vnum) chmin(ans, dp[gy][gx][i]); if (ans == INT32_MAX) ans = -1; out(ans); return 0; }