結果

問題 No.2855 Move on Grid
ユーザー tottoripaper
提出日時 2024-08-27 03:25:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 106 ms / 3,000 ms
コード長 1,700 bytes
コンパイル時間 2,066 ms
コンパイル使用メモリ 206,948 KB
最終ジャッジ日時 2025-02-24 02:27:34
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using ll = std::int64_t;
using T = std::tuple<int, int, int>;

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int N, M, K;
    std::cin >> N >> M >> K;

    std::vector A(N, std::vector<int>(M));
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            std::cin >> A[i][j];
        }
    }

    std::vector dist(N, std::vector<int>(M));
    std::deque<T> deque;
    int ok = 1, ng = 1'000'000'001;
    while(ng - ok >= 2){
        int m = (ok + ng) / 2;

        for(int i=0;i<N;i++){
            std::fill(std::begin(dist[i]), std::end(dist[i]), -1);
        }
        dist[0][0] = A[0][0] < m;
        deque.emplace_back(0, 0, dist[0][0]);

        while(!deque.empty()){
            auto [i, j, d] = deque.front();
            deque.pop_front();

            if(d != dist[i][j]){continue;}

            for(auto [di, dj] : std::initializer_list<std::tuple<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}){
                int ni = i + di;
                int nj = j + dj;
                if(ni < 0 || N <= ni || nj < 0 || M <= nj){
                    continue;
                }

                int c = A[ni][nj] < m;
                if(dist[ni][nj] == -1 || dist[ni][nj] > d + c){
                    dist[ni][nj] = d + c;
                    if(c == 0){
                        deque.emplace_front(ni, nj, dist[ni][nj]);
                    }else{
                        deque.emplace_back(ni, nj, dist[ni][nj]);
                    }
                }
            }
        }

        if(dist[N - 1][M - 1] <= K){
            ok = m;
        }else{
            ng = m;
        }
    }

    std::cout << ok << std::endl;
}
0