题解 P4205 【[NOI2005]智慧珠游戏 】
你们写的都太长了，发一个比较短的代码，时间为800ms
思路大概是，暴力枚举，还有一些剪枝。
用了一些奇技淫巧。
#include <bits/stdc++.h>
using namespace std;
const int N = 11;
const int n = 10;
const char *mmm[] =
{
"AA",
"A ",
"",
"BBBB",
"",
"CCC",
"C ",
"",
"DD",
"DD",
"",
"E ",
"E ",
"EEE",
"",
"FFFF",
" F ",
"",
"GGG",
"G G",
"",
"HHH",
"HH ",
"",
"III ",
" II",
"",
" J ",
"JJJ",
" J ",
"",
"K ",
"KK ",
" KK",
"",
"LLLL",
"L ",
"",
0
};
struct node
{
char state[5][5];
int fx;
int height;
int width;
node():fx(9999), height(0), width(0) {memset(state, 0, sizeof state);}
int fix()
{
if(fx != 9999) return fx;
for(int i = 0; i < width; ++i)
{
if(isalpha(state[0][i]))
return fx = i;
}
return -9999;
}
char *operator[](size_t i)
{
return state[i];
}
const char *operator[](size_t i) const
{
return state[i];
}
int ID()
{
return state[0][fix()];
}
node rotate() const
{
node nd;
nd.height = width;
nd.width = height;
for(int i = 0; i < width; ++i)
{
for(int j = 0; j < height; ++j)
nd[i][j] = state[j][width - 1 - i];
}
return nd;
}
node reverse() const
{
node nd;
nd.height = height;
nd.width = width;
for(int i = 0; i < height; ++i)
memcpy(nd[i], state[height - 1 -i], width + 1);
return nd;
}
void show()
{
for(int i = 0; i < height; ++i)
{
for (int j = 0; j < width; j++) {
cerr << state[i][j];
}
cerr << endl;
}
cerr << endl;
}
};
bool operator<(node &lhs, node &rhs)
{
if(lhs.ID() != rhs.ID()) return lhs.ID() < rhs.ID();
if(lhs.height != rhs.height) return lhs.height < rhs.height;
if(lhs.width != rhs.width) return lhs.width < rhs.width;
for(int i = 0; i < lhs.height; ++i)
if(strcmp(lhs[i], rhs[i]) != 0)
return strcmp(lhs[i], rhs[i]) < 0;
return false;
}
bool operator==(node &lhs, node &rhs)
{
return !(lhs < rhs) && !(rhs < lhs);
}
node mmp[12 * 8];
int len;
void init()
{
const char **p = mmm;
while(*p)
{
node nd;
while(*p && **p)
{
strcpy(nd[nd.height++], *p);
++p;
}
nd.width = strlen(nd[0]);
mmp[len++] = (nd);
mmp[len++] = (nd.rotate());
mmp[len++] = (nd.rotate().rotate());
mmp[len++] = (nd.rotate().rotate().rotate());
mmp[len++] = (nd.reverse());
mmp[len++] = (nd.rotate().reverse());
mmp[len++] = (nd.rotate().rotate().reverse());
mmp[len++] = (nd.rotate().rotate().rotate().reverse());
++p;
}
sort(mmp, mmp + len);
len = unique(mmp, mmp + len) - mmp;
random_shuffle(mmp, mmp + len);
}
int used[255];
char mp[N][N];
void show_map()
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
cout << mp[i][j];
cout << endl;
}
cout << endl;
}
bool check(int x, int y, int id)
{
const node &nd = mmp[id];
if(x + nd.height - 1 > n) return false;
if(y + nd.width - 1 > n) return false;
for(int i = 0; i < nd.height; ++i)
{
for(int j = 0; j < nd.width; ++j)
{
if(isalpha(nd[i][j]) && mp[x+i][y+j] != '.')
return false;
}
}
return true;
}
bool put(int x, int y, int id, bool unput)
{
const node &nd = mmp[id];
for(int i = 0; i < nd.height; ++i)
{
for(int j = 0; j < nd.width; ++j)
{
if(isalpha(nd[i][j]))
{
if(unput)
mp[x + i][y + j] = '.';
else
mp[x + i][y + j] = nd[i][j];
}
}
}
return true;
}
int pre[N*N];
int find(int i)
{
if(pre[i] > 0)
return pre[i] = find(pre[i]);
else return i;
}
void merge(int a, int b)
{
int ra = find(a), rb = find(b);
if(ra == rb) return;
pre[ra] -= -pre[rb] + 1;
pre[rb] = ra;
}
bool checkcn()
{
memset(pre, 0, sizeof pre);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
{
if(mp[i][j] == '.')
{
if(mp[i][j-1] == '.')
merge(i*n + j, i * n + j - 1);
if(mp[i-1][j] == '.')
merge(i*n + j, (i - 1) * n + j);
}
}
}
// for(int i = 1; i <= n; ++i)
// {
// for(int j = 1; j <= i; ++j)
// {
// cerr << -pre[find(i * n + j)] + 1 << " ";
// }
// cerr << endl;
// }
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
{
if(mp[i][j] == '.' && -pre[find(i * n + j)] + 1 < 3)
return false;
}
}
return true;
}
clock_t b ;
void dfs(int x, int y)
{
if(!checkcn())
{
return;
}
while(x <= n && isalpha(mp[x][y]))
{
++y;
if(y > x)
y = 1, x += 1;
}
if(x == n + 1)
{
show_map();
cerr << 1.0 * (clock() - b) / CLOCKS_PER_SEC << endl;
exit(0);
}
// show_map();
for(int i = 0; i < len; ++i)
{
int ny = y - mmp[i].fix();
if(!used[mmp[i].ID()] && check(x, ny, i))
{
put(x, ny, i, false);
used[mmp[i].ID()] = 1;
dfs(x, y + 1);
used[mmp[i].ID()] = 0;
put(x, ny, i, true);
}
}
}
#define IO(file) freopen(#file".in", "r", stdin), freopen(#file".out", "w", stdout)
int main()
{
IO(game);
// freopen("game.out", "w", stdout);
memset(mp, 'X', sizeof mp);
init();
// for(int i = 0; i < len; ++i) {
// cout << mmp[i].ID() << endl;
// mmp[i].show();
// }
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
{
cin >> mp[i][j];
if(isalpha(mp[i][j]))
{
used[mp[i][j]] = 1;
}
}
}
b = clock();
dfs(1, 1);
cout << "No solution" << endl;
}