結果
問題 | No.2675 KUMA |
ユーザー |
![]() |
提出日時 | 2024-03-15 22:14:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 1,848 bytes |
コンパイル時間 | 4,603 ms |
コンパイル使用メモリ | 309,540 KB |
実行使用メモリ | 7,892 KB |
最終ジャッジ日時 | 2024-09-30 01:35:56 |
合計ジャッジ時間 | 6,823 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using ll = long long; using ull = unsigned long long; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define REP(i, m, n) for(int i = (int)(m); i < (int)(n); i++) using namespace std; using namespace atcoder; using mint = modint998244353; const int inf = 1000000007; const ll longinf = 1ll << 60; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(1001, vector(1001, 0)); rep(i, n) { int x, y; cin >> x >> y; a[x][y] = 1 << i; } int all = 1 << n; vector<int> dp(all, inf); dp[0] = 0; auto get = [&](int x, int y) { if(0 <= x && x <= 1000 && 0 <= y && y <= 1000) { return a[x][y]; } else { return 0; } }; REP(x, -2, 1003) REP(y, -2, 1003) { if(get(x, y) > 0) { continue; } vector<int> vals; { int u = get(x + 2, y + 1) | get(x + 2, y - 1); if(u > 0) vals.push_back(u); } { int u = get(x - 2, y + 1) | get(x - 2, y - 1); if(u > 0) vals.push_back(u); } { int u = get(x + 1, y + 2) | get(x - 1, y + 2); if(u > 0) vals.push_back(u); } { int u = get(x + 1, y - 2) | get(x - 1, y - 2); if(u > 0) vals.push_back(u); } if(vals.size() > 0) { vector<int> ndp = dp; rep(i, all) for(auto v : vals) { ndp[i | v] = min(ndp[i | v], dp[i] + 1); } dp.swap(ndp); } } if(dp[all - 1] == inf) { cout << -1 << endl; } else { cout << dp[all - 1] << endl; } return 0; }