結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-09-12 02:26:46 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 815 ms / 3,000 ms |
コード長 | 1,745 bytes |
コンパイル時間 | 1,523 ms |
コンパイル使用メモリ | 168,744 KB |
実行使用メモリ | 147,568 KB |
最終ジャッジ日時 | 2024-11-17 03:47:06 |
合計ジャッジ時間 | 5,927 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,n) for(int i=0;i<n;i++)#define rep(i,n) for(int i=0;i<n;i++)#define INF 1<<29#define LINF LLONG_MAX/3#define MP make_pair#define PB push_back#define EB emplace_back#define ALL(v) (v).begin(),(v).end()#define debug(x) cerr<<#x<<":"<<x<<endl#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endltemplate<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; returnos; }typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<vi> vvi;const int dx[8]={0,-1,-1,-1,0,1,1,1};const int dy[8]={1,1,0,-1,-1,-1,0,1};int H,W;int main(){cin>>H>>W;vvi s(H+2,vi(W+2,0));vvi d(H+2,vi(W+2,INF));for(int i=1;i<=H;i++){string ss;cin>>ss;for(int j=0;j<W;j++){if(ss[j]=='#') s[i][j+1]=1;}}for(int i=0;i<H+2;i++) for(int j=0;j<W+2;j++) if(s[i][j]==0) d[i][j]=0;queue<pii> que;for(int i=0;i<H+2;i++) for(int j=0;j<W+2;j++) if(s[i][j]==0) que.push(pii(i,j));while(!que.empty()){auto p = que.front();que.pop();int x=p.first;int y=p.second;int di=d[x][y];for(int i=0;i<8;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx<0 or ny<0 or nx>=H+2 or ny>=W+2) continue;int nd=d[nx][ny];if(nd > di + 1){d[nx][ny] = di+1;que.push(pii(nx,ny));}}}int ans = 0;for(int i=0;i<H+2;i++){for(int j=0;j<W+2;j++){ans=max(ans,d[i][j]);}}cout << ans << endl;}