結果
問題 | No.2675 KUMA |
ユーザー |
|
提出日時 | 2024-03-13 22:35:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,904 bytes |
コンパイル時間 | 2,731 ms |
コンパイル使用メモリ | 256,708 KB |
実行使用メモリ | 8,896 KB |
最終ジャッジ日時 | 2024-09-29 23:38:42 |
合計ジャッジ時間 | 4,333 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> x(N), y(N); // その座標にいる UMA の集合を bit で持っておく。 int uma_set[1100][1100] = {}; for (int i = 0; i < N; i++) { cin >> x[i] >> y[i]; // 負になってバグるのを防ぐため +5 ずつしておく x[i] += 5; y[i] += 5; uma_set[x[i]][y[i]] = (1 << i); } // 設置する点の候補を列挙 set<pair<int, int>> candidates; const int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}; const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; for (int i = 0; i < N; i++) { for (int j = 0; j < 8; j++) { candidates.insert({x[i] + dx[j], y[i] + dy[j]}); } } // UMA のいる場所を除く for (int i = 0; i < N; i++) { pair<int, int> p = {x[i], y[i]}; if (candidates.count(p)) candidates.erase(p); } // dp vector<int> dp(1 << N, numeric_limits<int>::max()); dp[0] = 0; for (auto &&[a, b] : candidates) { auto new_dp = dp; for (int bits = 0; bits < (1 << N); bits++) { if (dp[bits] == numeric_limits<int>::max()) continue; const int dx1[] = {-1, -1, +2, -2}; const int dy1[] = {+2, -2, -1, -1}; const int dx2[] = {+1, +1, +2, -2}; const int dy2[] = {+2, -2, +1, +1}; for (int dir = 0; dir < 4; dir++) { int bits_next = bits; // 向いた先の UMA を bits_next に加える bits_next |= uma_set[a + dx1[dir]][b + dy1[dir]]; bits_next |= uma_set[a + dx2[dir]][b + dy2[dir]]; new_dp[bits_next] = min(new_dp[bits_next], dp[bits] + 1); } } dp.swap(new_dp); } cout << (dp.back() != numeric_limits<int>::max() ? dp.back() : -1) << endl; }