计算几何+搜索
AC 代码如下
#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r) for(int i = (l); i < (r); i++)
const double eps = 1e-6;
const double inf = 0x3f3f3f3f;
const int maxn = 10;
int n, m;
int dcmp(double x) {
if (fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
class Point {
public:
double x, y;
Point(double xx = 0, double yy = 0) : x(xx), y(yy) {}
Point operator+ (const Point &rhs) const {
return Point(x+rhs.x, y+rhs.y);
}
Point operator- (const Point &rhs) const {
return Point(x-rhs.x, y-rhs.y);
}
bool operator== (const Point &rhs) const {
return dcmp(x-rhs.x) == 0 && dcmp(y-rhs.y) == 0;
}
};
typedef Point Vector;
double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
bool onSegment(Point p, Point a1, Point a2) {
bool fl = dcmp( Cross(a1-p, a2-p) ) == 0 && dcmp( Dot(a1-p, a2-p) ) < 0;
return fl || (p == a1) || (p == a2);
}
const int RD = 2, LD = 3, RU = 4, LU = 5;
const int DOWN = 1, UP = 2, RIGHT = 3, LEFT = 4;
class Poly {
public:
int K;
Point a[105];
int mat[maxn][maxn];
int check(const Point &p) const {
int wn = 0;
_for(i, 0, K) {
if ( onSegment(p, a[i], a[(i+1)%K]) ) return 2;
int fl = dcmp( Cross(a[(i+1)%K]-a[i], p-a[i]) );
int d1 = dcmp( a[i].y - p.y );
int d2 = dcmp( a[(i+1)%K].y - p.y );
if (fl > 0 && d1 <= 0 && d2 > 0) wn++;
if (fl < 0 && d2 <= 0 && d1 > 0) wn--;
}
if (wn != 0) return 1;
return 0;
}
void buildMap() {
_for(i, 0, m) _for(j, 0, m) {
Point mid( (double)(i) + 0.5, (double)(j) + 0.5 );
Point lu( (double)(i) + 0.25, (double)(j) + 0.75 );
Point ru( (double)(i) + 0.75, (double)(j) + 0.75 );
Point ld( (double)(i) + 0.25, (double)(j) + 0.25 );
Point rd( (double)(i) + 0.75, (double)(j) + 0.25 );
if (check(mid) == 0) mat[i][j] = 0;
else if (check(mid) == 1) mat[i][j] = 1;
else if (check(ld) == 2 && check(ru) == 2 && check(rd) == 1) mat[i][j] = RD;
else if (check(lu) == 2 && check(rd) == 2 && check(ld) == 1) mat[i][j] = LD;
else if (check(lu) == 2 && check(rd) == 2 && check(ru) == 1) mat[i][j] = RU;
else mat[i][j] = LU;
}
}
double Area() {
double ans = 0.0;
_for(i, 0, m) _for(j, 0, m) {
if (mat[i][j] == 1) ans += 1;
else if (mat[i][j] != 0) ans += 0.5;
}
return ans;
}
void normalize() {
double xmin = inf, ymin = inf;
_for(i, 0, K) {
xmin = min(xmin, a[i].x);
ymin = min(ymin, a[i].y);
}
_for(i, 0, K) {
a[i].x -= xmin;
a[i].y -= ymin;
assert(0 <= a[i].x && a[i].x <= m);
assert(0 <= a[i].y && a[i].y <= m);
}
buildMap();
}
void rotate() {
_for(i, 0, K) {
a[i] = Point(a[i].y, -a[i].x);
}
normalize();
}
bool Move(int dir) {
if (dir == DOWN) {
_for(i, 0, m) if (mat[i][0] != 0) return false;
_for(j, 0, m-1) {
_for(i, 0, m) mat[i][j] = mat[i][j+1];
}
_for(i, 0, m) mat[i][m-1] = 0;
}
if (dir == UP) {
_for(i, 0, m) if (mat[i][m-1] != 0) return false;
for (int j = m-1; j > 0; j--) {
_for(i, 0, m) mat[i][j] = mat[i][j-1];
}
_for(i, 0, m) mat[i][0] = 0;
}
if (dir == RIGHT) {
_for(i, 0, m) if (mat[m-1][i] != 0) return false;
for (int i = m-1; i > 0; i--) {
_for(j, 0, m) mat[i][j] = mat[i-1][j];
}
_for(i, 0, m) mat[0][i] = 0;
}
if (dir == LEFT) {
_for(i, 0, m) if (mat[0][i] != 0) return false;
_for(i, 0, m-1) {
_for(j, 0, m) mat[i][j] = mat[i+1][j];
}
_for(i, 0, m) mat[m-1][i] = 0;
}
return true;
}
} poly[maxn];
vector<Poly> vec[maxn];
bool vis[maxn];
void getPolys() {
_for(i, 0, maxn) vec[i].clear();
memset(vis, 0, sizeof(vis));
_for(i, 0, n) {
Poly pp = poly[i];
// enumerate posture
_for(dir, 0, 4) {
Poly plg = pp;
while (true) {
Poly plgp = plg;
while (true) {
vec[i].push_back(plgp);
if (!plgp.Move(RIGHT)) break;
}
if (!plg.Move(UP)) break;
}
pp.rotate();
}
}
}
class Node {
public:
int mat[maxn][maxn];
void init() {
memset(mat, 0, sizeof(mat));
}
bool add(const Poly &p) {
_for(i, 0, m) _for(j, 0, m) {
if (mat[i][j] == 0) mat[i][j] = p.mat[i][j];
else {
if (p.mat[i][j] == 0) continue;
else if (mat[i][j] + p.mat[i][j] == 7) mat[i][j] = 1;
else return false;
}
}
return true;
}
} P;
bool dfs(int x, int y) {
if (y == m) return true;
bool ok = false;
if (P.mat[x][y] == 1) {
x++;
if (x == m) {
x = 0;
y++;
}
return dfs(x, y);
}
for (int i = 0; i < n && !(ok); i++) {
if (vis[i]) continue;
for (auto u : vec[i]) {
if (ok) break;
Node P0 = P;
// then try to insert
if (P.mat[x][y] == 0 && u.mat[x][y] != 0 && P.add(u)) {
vis[i] = true;
if (u.mat[x][y] != 1) ok = dfs(x, y);
else if (x == m-1) ok = dfs(0, y+1);
else ok = dfs(x+1, y);
vis[i] = false;
}
else if (P.mat[x][y] + u.mat[x][y] == 7 && P.add(u)) {
vis[i] = true;
if (x == m-1) ok = dfs(0, y+1);
else ok = dfs(x+1, y);
vis[i] = false;
}
P = P0;
}
}
return ok;
}
int main() {
int kase;
scanf("%d", &kase);
while (kase--) {
scanf("%d%d", &n, &m);
_for(i, 0, n) {
scanf("%d", &poly[i].K);
_for(j, 0, poly[i].K) {
scanf("%lf%lf", &poly[i].a[j].x, &poly[i].a[j].y);
}
}
double area = 0;
_for(i, 0, n) {
poly[i].normalize();
area += poly[i].Area();
}
if (dcmp(area - (m * m))) {
printf("no\n");
continue;
}
P.init();
getPolys();
int res = dfs(0, 0);
if (res) printf("yes\n");
else printf("no\n");
}
}
繁文缛节的搜索
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;
#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)
pair<int, int> crack(int n) {
int st = sqrt(n);
int fac = n / st;
while (n % st) {
st += 1;
fac = n / st;
}
return make_pair(st, fac);
}
inline ll qpow(ll a, int n) {
ll ans = 1;
for(; n; n >>= 1) {
if(n & 1) ans *= 1ll * a;
a *= a;
}
return ans;
}
template <class T>
inline bool chmax(T& a, T b) {
if(a < b) {
a = b;
return true;
}
return false;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll ksc(ll a, ll b, ll mod) {
ll ans = 0;
for(; b; b >>= 1) {
if (b & 1) ans = (ans + a) % mod;
a = (a * 2) % mod;
}
return ans;
}
ll ksm(ll a, ll b, ll mod) {
ll ans = 1 % mod;
a %= mod;
for(; b; b >>= 1) {
if (b & 1) ans = ksc(ans, a, mod);
a = ksc(a, a, mod);
}
return ans;
}
template <class T>
inline bool chmin(T& a, T b) {
if(a > b) {
a = b;
return true;
}
return false;
}
bool _check(int x) {
//
return true;
}
int bsearch1(int l, int r) {
while (l < r) {
int mid = (l + r) >> 1;
if(_check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int bsearch2(int l, int r) {
while (l < r) {
int mid = (l + r + 1) >> 1;
if(_check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
int n = a.size(), m = b.size();
int i;
for(i = 0; i < n && i < m; i++) {
if (a[i] < b[i]) return true;
else if (b[i] < a[i]) return false;
}
return (i == n && i < m);
}
// ============================================================== //
const int inf = 100;
const int maxn = 5;
const int maxl = 15;
int mat[maxn][maxn][maxn];
int a[maxn][maxl][maxn];
int n, m, K;
void prework(int p) {
K = 0;
_for(x, 0, m) {
_for(y, 0, m) a[p][K][y] = mat[p][x][y];
K++;
}
_for(y, 0, m) {
_for(x, 0, m) a[p][K][x] = mat[p][x][y];
K++;
}
_for(x, 0, m) {
a[p][K][x] = mat[p][x][x];
}
K++;
_for(x, 0, m) {
a[p][K][x] = mat[p][x][m-1-x];
}
K++;
assert(K == 2*m + 2);
}
int tim[inf + 5];
bool isChose[inf + 5];
bool mark[inf << 1];
bool isBingo(int p) {
// check card p is bingo
// check horizontal
_for(x, 0, m) {
bool ok = true;
_for(y, 0, m) if (!mark[ mat[p][x][y] ]) { ok = false; break; }
if (ok) return true;
}
// check vertical
_for(y, 0, m) {
bool ok = true;
_for(x, 0, m) if (!mark[ mat[p][x][y] ]) { ok = false; break; }
if (ok) return true;
}
// check slash 1
bool ok = true;
_for(x, 0, m) if (!mark[ mat[p][x][x] ]) { ok = false; break; }
if (ok) return true;
// check slash 2
ok = true;
_for(x, 0, m) if (!mark[ mat[p][x][m-1-x] ]) { ok = false; break; }
if (ok) return true;
return false;
}
bool isComplete() {
_for(i, 0, n-1) if (!isBingo(i)) return false;
return true;
}
bool valid() {
bool ok = true;
for (int i = 0; i < n; i++) {
if (isBingo(i)) {
if (!ok) return false;
}
else ok = false;
}
return true;
}
bool vis[1<<16];
int res = inf;
inline int cal() {
// calculate the last card
int ans = m+1;
_for(i, 0, K) {
int cnt = 0;
_for(j, 0, m) if (!mark[ a[n-1][i][j] ]) cnt++;
chmin(ans, cnt);
}
return ans;
}
void dfs2(const vector<int>& arr, int cnt, int sta) {
if (vis[sta]) return;
vis[sta] = true;
if (!valid()) return;
if (isComplete()) {
res = min(res, cnt + cal());
//debug(res);
return;
}
// then enumerate permutation of arr
for (int i = 0; i < arr.size(); i++) {
int x = arr[i];
if (mark[x]) continue;
mark[x] = true;
dfs2(arr, cnt + 1, sta | (1<<i));
mark[x] = false;
}
}
void dfs(int x) {
if (x == n-1) {
vector<int> arr;
for (int i = 0; i < inf; i++) {
if (isChose[i]) { arr.push_back(i); mark[i] = false; }
}
_for(i, 0, 1<<(arr.size())) vis[i] = 0;
dfs2(arr, 0, 0);
return;
}
for (int i = 0; i < K; i++) {
// enumerate bingo posture i for card x
_for(j, 0, m) {
int val = a[x][i][j];
if (tim[val] == -1) {
tim[val] = x;
isChose[val] = true;
}
}
dfs(x+1);
_for(j, 0, m) {
int val = a[x][i][j];
if (tim[val] == x) {
tim[val] = -1;
isChose[val] = false;
}
}
}
}
void init() {
memset(a, 0, sizeof(a));
memset(tim, -1, sizeof(tim));
memset(isChose, 0, sizeof(isChose));
memset(mark, 0, sizeof(mark));
memset(vis, 0, sizeof(vis));
K = 0;
res = inf;
}
int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &m) == 2 && n) {
init();
// get data
_for(i, 0, n) {
_for(x, 0, m) _for(y, 0, m) scanf("%d", &mat[i][x][y]);
}
// prework and normalize
_for(i, 0, n) prework(i);
// then solve
dfs(0);
if (res == inf) printf("0\n");
else printf("%d\n", res);
}
}
好长 tql
tql
tql