結果
| 問題 | No.157 2つの空洞 |
| ユーザー |
 wunderkammer2
|
| 提出日時 | 2021-06-25 12:55:21 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,980 bytes |
| コンパイル時間 | 1,088 ms |
| コンパイル使用メモリ | 105,220 KB |
| 最終ジャッジ日時 | 2024-11-15 01:28:21 |
| 合計ジャッジ時間 | 1,666 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'int calc(int, int, vs&, UnionFind&)':
main.cpp:208:12: error: 'numeric_limits' was not declared in this scope
208 | return numeric_limits<int>().max();
| ^~~~~~~~~~~~~~
main.cpp:208:27: error: expected primary-expression before 'int'
208 | return numeric_limits<int>().max();
| ^~~
main.cpp:208:27: error: expected ';' before 'int'
208 | return numeric_limits<int>().max();
| ^~~
| ;
main.cpp:208:30: error: expected unqualified-id before '>' token
208 | return numeric_limits<int>().max();
| ^
main.cpp: In function 'int main()':
main.cpp:238:15: error: 'numeric_limits' was not declared in this scope
238 | int ans = numeric_limits<int>().max();
| ^~~~~~~~~~~~~~
main.cpp:238:30: error: expected primary-expression before 'int'
238 | int ans = numeric_limits<int>().max();
| ^~~
ソースコード
#include<algorithm> //sort,二分探索,など
#include<bitset> //固定長bit集合
#include<cmath> //pow,logなど
#include<complex> //複素数
#include<deque> //両端アクセスのキュー
#include<fstream> //ファイルストリーム（標準入力変更用）
#include<functional> //sortのgreater
#include<iomanip> //setprecision(浮動小数点の出力の誤差)
#include<iostream> //入出力
#include<iterator> //集合演算(積集合,和集合,差集合など)
#include<map> //map(辞書)
#include<numeric> //iota(整数列の生成),gcdとlcm(c++17)
#include<queue> //キュー
#include<set> //集合
#include<stack> //スタック
#include<string> //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility> //pair
#include<vector> //可変長配列
//#include<atcoder\all>
//using namespace atcoder;
//名前
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef map<string, int> msi;
typedef map<string, ll> msll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pllll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
//定数
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
const int MAXR = 100000; //10^5:配列の最大のrange
//マクロ
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,s,e) for(int i=s;i<e;i++)
#define repse(i,s,e) for(int i=s;i<=e;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define in1(x1) cin >> x1
#define in2(x1, x2) cin >> x1 >> x2
#define in3(x1, x2, x3) cin >> x1 >> x2 >> x3
#define in4(x1, x2, x3, x4) cin >> x1 >> x2 >> x3 >> x4
#define in5(x1, x2, x3, x4, x5) cin >> x1 >> x2 >> x3 >> x4 >> x5
#define in6(x1, x2, x3, x4, x5, x6) cin >> x1 >> x2 >> x3 >> x4 >> x5 >> x6
#define inN(x, N) rep(i, N) in1(x[i])
#define outl(x) cout << x << endl
#define out2l(x, y) cout << x << " " << y << endl
#define out3l(x1, x2, x3) cout << x1 << " " << x2 << " " << x3 << endl
#define out4l(x1, x2, x3, x4) cout << x1 << " " << x2 << " " << x3 << " " << x4 << endl
#define outList(x) for(auto y : x) cout << y << " ";cout << endl
//よく使う関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
inline ll div_ceil(ll a, ll b) { return (a + (b - 1)) / b; }
inline string zeropad(int n, int m) { ostringstream sout; sout << setfill('0') << setw(m) << n; return sout.str(); }
class UnionFind
{
//par[i]：ノードiの親
//count[i]：iが親の時、iが属するグループのノード数
vector<int> par;
vector<int> count;
int m_groupCount = 0;
public:
UnionFind(int N)
{
//1始まりのときに必要
//par.push_back(0);
//count.push_back(0);
m_groupCount = N;
rep(i, N)
{
//最初は全てが根であるとして初期化
par.push_back(i);
count.push_back(1);
}
}
//データxが属する木の根を再帰で得る：root(x) = {xの木の根}
int root(int x)
{
if (par[x] == x) return x;
//ついでに親を張り替え
return par[x] = root(par[x]);
}
//xとyの木を併合
void unite(int x, int y)
{
int rx = root(x);
int ry = root(y);
if (rx == ry) return;
//xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
par[rx] = ry;
//要素数の変更
count[ry] += count[rx];
count[rx] = 0;
//木の併合によってグループが1つ減る
m_groupCount--;
}
// 2つのデータx, yが属する木が同じならtrueを返す
bool same(int x, int y)
{
return root(x) == root(y);
}
//指定したデータxが属するグループの要素数を返す
int size(int x)
{
return count[root(x)];
}
//UnionFindのグループの個数を返す
int groupCount()
{
return m_groupCount;
}
//UnionFindのコピー処理
UnionFind copy()
{
UnionFind uf(par.size());
//元のUnionFindの親情報を再現
rep(i, par.size())
{
uf.unite(i, this->root(i));
}
return uf;
}
};
int H, W;
int rctoi(int h, int w)
{
return h * W + w;
}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int calc(int h, int w, vs &C, UnionFind &uf)
{
queue<pii> q;
q.emplace(h, w);
vvi d(H, vi(W, -1));
d[h][w] = 0;
while (!q.empty())
{
auto p = q.front(); q.pop();
rep(i, 4)
{
int x = p.first + dx[i];
int y = p.second + dy[i];
if (!(x >= 0 && x < H && y >= 0 && y < W)) continue;
if (d[x][y] != -1) continue;
if(uf.same(rctoi(h, w), rctoi(x, y))) continue;
q.emplace(x, y);
d[x][y] = d[p.first][p.second];
if (C[x][y] == '.')
{
return d[x][y];
}
else
{
d[x][y]++;
}
}
}
return numeric_limits<int>().max();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//標準入力をファイルに変更
//std::ifstream in("input.txt");
//std::cin.rdbuf(in.rdbuf());
in2(W, H);
vs C(H);
inN(C, H);
UnionFind uf(H * W);
rep(i, H) rep(j, W) rep(k, 4)
{
int x = i + dx[k];
int y = j + dy[k];
if (!(x >= 0 && x < H && y >= 0 && y < W)) continue;
if (C[i][j] == C[x][y]) uf.unite(rctoi(i, j), rctoi(x, y));
}
int ans = numeric_limits<int>().max();
rep(i, H) rep(j, W)
{
if (C[i][j] == '.')
{
chmin(ans, calc(i, j, C, uf));
}
}
outl(ans);
return 0;
}