結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-22 23:01:06 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 586 ms / 3,000 ms |
コード長 | 1,433 bytes |
コンパイル時間 | 2,125 ms |
コンパイル使用メモリ | 165,784 KB |
実行使用メモリ | 112,216 KB |
最終ジャッジ日時 | 2024-11-06 12:57:11 |
合計ジャッジ時間 | 5,127 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; typedef long long ll; typedef pair<int,int> ii; #include <string> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; typedef pair<int,int> ii; int dir[8][2] = {{1,1},{1,-1},{-1,1},{-1,-1},{1,0},{-1,0},{0,1},{0,-1}}; int n,m; bool isok(int a,int b){ return a>=0 && a<=n+1 && b>=0 && b<=m+1; } int r[3003][3003]; int main() { memset(r,-1,sizeof(r)); ios::sync_with_stdio(false); queue<ii> bfs; cin>>n>>m; string t; for(int ctr1=0;ctr1<=m+1;ctr1++) bfs.push({0,ctr1}),r[0][ctr1]=0; for(int ctr1=1;ctr1<=n;ctr1++){ bfs.push({ctr1,0}),r[ctr1][0]=0; cin>>t; for(int ctr2=0;ctr2<m;ctr2++){ if(t[ctr2]=='.') bfs.push({ctr1,ctr2+1}),r[ctr1][ctr2+1]=0; } bfs.push({ctr1,m+1}),r[ctr1][m+1]=0; } for(int ctr1=0;ctr1<=m+1;ctr1++) bfs.push({n+1,ctr1}),r[n+1][ctr1]=0; int rez=0; while(!bfs.empty()){ ii cur=bfs.front(); bfs.pop(); for(int ctr2=0;ctr2<8;ctr2++) if(isok(cur.first+dir[ctr2][0],cur.second+dir[ctr2][1]) && r[cur.first+dir[ctr2][0]][cur.second+dir[ctr2][1]]==-1) bfs.push({cur.first+dir[ctr2][0],cur.second+dir[ctr2][1]}),rez=r[cur.first+dir[ctr2][0]][cur.second+dir[ctr2][1]]=r[cur.first][cur.second]+1; } cout<<rez; return 0; }