結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-23 01:27:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,152 ms / 3,000 ms |
コード長 | 2,779 bytes |
コンパイル時間 | 1,513 ms |
コンパイル使用メモリ | 121,676 KB |
実行使用メモリ | 203,988 KB |
最終ジャッジ日時 | 2024-11-06 14:16:01 |
合計ジャッジ時間 | 7,025 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream>#include <string>#include <queue>#include <stack>#include <algorithm>#include <list>#include <vector>#include <complex>#include <utility>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <climits>#include <bitset>#include <ctime>#include <map>#include <unordered_map>#include <set>#include <unordered_set>#include <cassert>#include <cstddef>#include <iomanip>#include <numeric>#include <tuple>#include <sstream>#include <fstream>#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)#define FOR(i,a,b) for(long (i)=(a);(i)<(b);(i)++)#define RREP(i,a) for(long (i)=(a)-1;(i)>=0;(i)--)#define FORR(i,a,b) for(long (i)=(a)-1;(i)>=(b);(i)--)#define PI acos(-1.0)#define DEBUG(C) cout<<C<<endl;#define VI vector<int>#define VII vector<VI>#define VL vector<long>#define VLL vector<VL>#define VD vector<double>#define VDD vector<VD>#define PII pair<int,int>#define PDD pair<double,double>#define PLL pair<long,long>#define ALL(a) (a).begin(),(a).end()#define SORT(a) sort(ALL(a))#define REVERSE(a) reverse(ALL(a))#define MP make_pair#define FORE(a,b) for(auto &&a:b)using namespace std;typedef long long LL;typedef unsigned long long ULL;const int INF=1e9;const int MOD=INF+7;VII dis;vector<string> S;int H,W;int vh[]={0,0,-1,-1,-1,1,1,1};int vw[]={1,-1,1,0,-1,1,0,-1};queue<PII> q;void search(){while(!q.empty()){PII p=q.front(); q.pop();int ph=p.first,pw=p.second;REP(i,8){int dh=ph+vh[i],dw=pw+vw[i];if(dh>=H+2 || dh<0) continue;if(dw>=W+2 || dw<0) continue;if(dis[dh][dw]==-1) continue;if(dis[ph][pw]==-1){dis[dh][dw]=1;q.push(MP(dh,dw));}else if(dis[dh][dw]==0 || dis[dh][dw]>dis[ph][pw]+1){dis[dh][dw]=dis[ph][pw]+1;q.push(MP(dh,dw));}}}}void out(){REP(i,dis.size()){REP(j,dis[i].size()){cout<<dis[i][j]<<" ";}cout<<endl;}}void sout(){REP(i,S.size()){REP(j,S[i].size()){cout<<S[i][j]<<" ";}cout<<endl;}}string str(char c,int n){string ret="";while(n--) ret+=c;return ret;}int main (void){cin>>H>>W;S=vector<string>(H+2);S.front()=str('.',W);S.back()=S.front();FOR(i,1,H+1) cin>>S[i];REP(i,S.size()){S[i]='.'+S[i]+'.';}dis=VII(H+2,VI(W+2,0));REP(i,H+2)REP(j,W+2){if(S[i][j]=='.'){dis[i][j]=-1;q.push(MP(i,j));}}search();int ans=1;REP(i,H+2)REP(j,W+2){ans=max(ans,dis[i][j]);}//sout();cout<<ans<<endl;}