結果
問題 | 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 1000000007using 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;}