結果
問題 |
No.402 最も海から遠い場所
|
ユーザー |
![]() |
提出日時 | 2024-11-12 15:37:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 659 ms / 3,000 ms |
コード長 | 900 bytes |
コンパイル時間 | 1,797 ms |
コンパイル使用メモリ | 174,316 KB |
実行使用メモリ | 93,108 KB |
最終ジャッジ日時 | 2024-11-12 15:37:38 |
合計ジャッジ時間 | 6,009 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int N=3010; int n,m,ans,dis[N][N]; string a[N]; queue<int> q; signed main(){ // freopen("1.in","r",stdin); ios::sync_with_stdio(0); cin>>n>>m; for(int i=0;i<=m+1;i++){ a[0]+='.'; a[n+1]+='.'; } for(int i=1;i<=n;i++){ cin>>a[i]; a[i]="."+a[i]+"."; } // cerr<<"input done\n"; memset(dis,0x3f,sizeof(dis)); for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ if(a[i][j]=='.') dis[i][j]=0,q.push(i*10000+j); } } while(!q.empty()){ int now=q.front(),i=now/10000,j=now%10000; q.pop(); // cout<<i<<" "<<j<<'\n'; for(int nxt=0;nxt<=8;nxt++){ int ni=i+(nxt/3-1),nj=j+(nxt%3-1); // cout<<(nxt/3-1)<<" "<<(nxt%3-1)<<'\n'; if(ni<0||ni>n+1||nj<0||nj>m+1) continue; if(dis[ni][nj]>dis[i][j]+1){ dis[ni][nj]=dis[i][j]+1; ans=max(ans,dis[ni][nj]); q.push(ni*10000+nj); } } } cout<<ans<<'\n'; return 0; }