結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <queue>#define rep(i, n) for(i = 0; i < n; i++)#define int long longusing 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;}