結果
問題 | No.157 2つの空洞 |
ユーザー |
|
提出日時 | 2015-03-03 21:40:56 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,878 bytes |
コンパイル時間 | 1,049 ms |
コンパイル使用メモリ | 98,528 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 01:16:55 |
合計ジャッジ時間 | 1,589 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:46:13: warning: ‘sx’ may be used uninitialized in this function [-Wmaybe-uninitialized] 46 | c[sy][sx] = '!'; | ^ main.cpp:46:9: warning: ‘sy’ may be used uninitialized in this function [-Wmaybe-uninitialized] 46 | c[sy][sx] = '!'; | ^
ソースコード
#include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> using namespace std; const int dy[] = {-1, 0, 1, 0}; const int dx[] = {0, -1, 0, 1}; int main() { int w, h; cin >> w >> h; vector<string> c(h+2, string(w+2, '!')); int sy, sx; for(int y=1; y<=h; ++y){ for(int x=1; x<=w; ++x){ cin >> c[y][x]; if(c[y][x] == '.'){ sy = y; sx = x; } } } queue<pair<int, int> > q1, q2; q1.push(make_pair(sy, sx)); q2.push(make_pair(sy, sx)); c[sy][sx] = '!'; while(!q1.empty()){ int y = q1.front().first; int x = q1.front().second; q1.pop(); for(int i=0; i<4; ++i){ int y2 = y + dy[i]; int x2 = x + dx[i]; if(c[y2][x2] == '.'){ q1.push(make_pair(y2, x2)); q2.push(make_pair(y2, x2)); c[y2][x2] = '!'; } } } int ret = 0; for(;;){ int n = q2.size(); while(--n >= 0){ int y = q2.front().first; int x = q2.front().second; q2.pop(); for(int i=0; i<4; ++i){ int y2 = y + dy[i]; int x2 = x + dx[i]; if(c[y2][x2] == '.'){ cout << ret << endl; return 0; } if(c[y2][x2] == '#'){ q2.push(make_pair(y2, x2)); c[y2][x2] = '!'; } } } ++ ret; } }