結果

問題 No.2855 Move on Grid
ユーザー startcpp
提出日時 2024-08-25 14:44:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 215 ms / 3,000 ms
コード長 1,288 bytes
コンパイル時間 661 ms
コンパイル使用メモリ 79,700 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-08-25 14:45:00
合計ジャッジ時間 7,898 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
int INF = 1e+9;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int n, m, K;
int a[300][300];
int dp[300][300];
bool check(int X) {
int i, j;
rep(i, n) rep(j, m) dp[i][j] = INF;
queue<P> que[2];
que[0].push(P(0, 0));
dp[0][0] = (a[0][0] < X);
while (que[0].size() + que[1].size() > 0) {
P now;
if (!que[0].empty()) { now = que[0].front(); que[0].pop(); }
else { now = que[1].front(); que[1].pop(); }
int y = now.first;
int x = now.second;
rep(i, 4) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
if (a[ny][nx] < X && dp[ny][nx] > dp[y][x] + 1) {
que[1].push(P(ny, nx));
dp[ny][nx] = dp[y][x] + 1;
}
if (a[ny][nx] >= X && dp[ny][nx] > dp[y][x]) {
que[0].push(P(ny, nx));
dp[ny][nx] = dp[y][x];
}
}
}
return dp[n - 1][m - 1] <= K;
}
signed main() {
int i, j;
cin >> n >> m >> K;
rep(i, n) rep(j, m) cin >> a[i][j];
int ok = 0, ng = 1000000001, mid;
while (ng - ok >= 2) {
mid = (ok + ng) / 2;
if (check(mid)) ok = mid;
else ng = mid;
}
cout << ok << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0