結果

問題 No.402 最も海から遠い場所
コンテスト
ユーザー vjudge1
提出日時 2024-11-08 22:39:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,522 bytes
コンパイル時間 1,256 ms
コンパイル使用メモリ 112,844 KB
実行使用メモリ 296,984 KB
最終ジャッジ日時 2024-11-08 22:39:20
合計ジャッジ時間 5,996 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 9 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#define rep(i, l, r) for (int i = (l); i <= (r); i ++ )
#define per(i, r, l) for (int i = (r); i >= (l); i -- )
 
using namespace std;
 
const int N = 3005, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int n, m;
double x[N][N], y[N][N], dis[N][N];
char ch[N][N];
 
int main() {
 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    rep(i, 1, n) rep(j, 1, m) cin >> ch[i][j], x[i][j] = (i + j) * 1.0 / 2, y[i][j] = (i - j) * 1.0 / 2;
    queue<pair<int, int> > q;
    rep(i, 1, n) rep(j, 1, m) if (ch[i][j] == '.') q.push({i, j}), dis[i][j] = 0; else dis[i][j] = 1e9;
    rep(i, 0, n + 1) rep(j, 0, m + 1) if (i == 0 || j == 0 || i == n + 1 || j == m + 1) q.push({i, j}), x[i][j] = (i + j) * 1.0 / 2, y[i][j] = (i - j) * 1.0 / 2;
    while (!q.empty()) {
        auto t = q.front(); q.pop();
        for (int i = 0; i < 4; i ++ ) {
            int nx = t.first + dx[i], ny = t.second + dy[i];
            if (nx < 0 || ny < 0 || nx > n + 1 || ny > m + 1) continue;
            if (dis[nx][ny] > dis[t.first][t.second] + fabs(x[nx][ny] - x[t.first][t.second]) + fabs(y[nx][ny] - y[t.first][t.second])) {
                dis[nx][ny] = dis[t.first][t.second] + fabs(x[nx][ny] - x[t.first][t.second]) + fabs(y[nx][ny] - y[t.first][t.second]);
                q.push({nx, ny});
            }
        }
    }
    double ans = 0;
    rep(i, 1, n) rep(j, 1, m) ans = max(ans, dis[i][j]);
    cout << (int)ans << '\n';
 
    return 0;
}
0