結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー ctyl_0
提出日時 2015-09-16 19:08:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 43 ms / 5,000 ms
コード長 2,839 bytes
コンパイル時間 878 ms
コンパイル使用メモリ 98,732 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 05:27:17
合計ジャッジ時間 1,744 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <climits>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int cost(pair<int, int> start, pair<int, int> goal, vector<vector<int>> L, int N, int V){
    
    vector<vector<bool>> isVis(N, vector<bool>(N));
    int ret = V;
    // priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push(make_pair(ret, start));
    
    while (!pq.empty()) {
        int v = pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
        
        if (isVis[x][y]) {
            continue;
        }
        isVis[x][y] = true;
        
        if (x == goal.first && y == goal.second) {
            ret = v;
            break;
        }
        
        rep(i, 4){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N || isVis[nx][ny] == true) {
                continue;
            }
            int nv = v - L[nx][ny];
            pq.push(make_pair(nv, make_pair(nx, ny)));
        }
    }
    
    return ret;
}

int main(int argc, const char * argv[]) {
    
    // source code
    int N = inputValue(); // 一辺 200
    int V = inputValue(); // 体力 500
    pair<int, int> O = make_pair(inputValue() - 1, inputValue() - 1); // オアシスの位置
    vector<vector<int>> L(N, vector<int>(N)); // 減る体力
    
    rep(i, N){
        rep(j, N){
            L[i][j] = inputValue();
        }
    }

    int costStartGoal = V - cost(make_pair(0, 0), make_pair(N - 1, N - 1), L, N, V);
    int costStartOasis = 1000;
    int costOasisGoal = 1000;
    if (O.first >= 0 && O.second >= 0) {
        costStartOasis = V - cost(make_pair(0, 0), O, L, N ,V);
        costOasisGoal = V - cost(O, make_pair(N - 1, N - 1), L, N, V);
    }
    
    
    if (costStartGoal < V || 2 * (V - costStartOasis) - costOasisGoal > 0) {
        output("YES", 0);
    }
    else{
        output("NO", 0);
    }
    
    
    
    
    
    return 0;
}
0