| 记录编号 |
185236 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[NOIP 2010冲刺七]翻转游戏 |
最终得分 |
100 |
| 用户昵称 |
 啊吧啦吧啦吧 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.114 s |
| 提交时间 |
2015-09-05 10:59:56 |
内存使用 |
1.01 MiB |
显示代码纯文本
#include <iostream>
#include <queue>
#include <fstream>
#include <cstdlib>
#include <algorithm>
using namespace std;
ofstream fout("flip.out");
#define cout fout
#define cin fin
struct off_void{
inline void a(){
cout << "Impossible";
fout.close();
// for (; ; );
exit(0);
}
inline void b(int x){
// cout << f[24479] << endl << g[24479] << endl << h[24479] << endl;
cout << x;
fout.close();
// for (; ; );
exit(0);
}
} off;
//b->0,w->1.
int ans, nmap = 0, f[65536], g[65536], h[65536];
bool map[5][5];
char c;
ifstream fin("flip.in");
inline void bfs();
queue<int> qm, qb, qw;
main()
{
for (int i = 1; i <= 4; ++i)
for (int j = 1; j < 5; ++j){
cin >> c;
map[i][j] = c == 'w';
nmap = nmap << 1 | map[i][j];
}
fin.close();
// cout << nmap << endl;
if (nmap == 0 || nmap == 65535)
off.b(0);
bfs();
off.a();
}
inline void bfs(){
fill(f, f + 65536, -1);
fill(g, g + 65536, -1);
fill(h, h + 65535, -1);
f[nmap] = 0;
qm.push(nmap);
g[0] = 0;
qb.push(0);
h[65535] = 0;
qw.push(65535);
while ((!qm.empty()) && (!qb.empty()) && (!qw.empty())){
int fr = qm.front(), peo = fr;
qm.pop();
for (int i = 4; i > 0; --i)
for (int j = 4; j > 0; --j){
map[i][j] = peo & 1;
peo >>= 1;
// cout << map[i][j];
}
for (int i = 1; i < 5; ++i)
for (int j = 1; j < 5; ++j){
map[i][j] = ! map[i][j];
if (i - 1 > 0)
map[i - 1][j] = ! map[i - 1][j];
if (j - 1 > 0)
map[i][j - 1] = ! map[i][j - 1];
if (i + 1 < 5)
map[i + 1][j] = ! map[i + 1][j];
if (j + 1 < 5)
map[i][j + 1] = ! map[i][j + 1];
nmap = 0;
for (int k = 1; k < 5; ++k) //{
for (int l = 1; l < 5; ++l) {
// cout << map[k][l];
nmap = nmap << 1 | map[k][l];
}
// cout << endl;
// }
// cout << nmap << endl;
map[i][j] = ! map[i][j];
if (i - 1 > 0)
map[i - 1][j] = ! map[i - 1][j];
if (j - 1 > 0)
map[i][j - 1] = ! map[i][j - 1];
if (i + 1 < 5)
map[i + 1][j] = ! map[i + 1][j];
if (j + 1 < 5)
map[i][j + 1] = ! map[i][j + 1];
if (f[nmap] >= 0)
continue;
else{
f[nmap] = f[fr] + 1;
qm.push(nmap);
int end = 0;
if (g[nmap] >= 0)
end = g[nmap] + f[nmap];
if (h[nmap] >= 0)
end = min(end, h[nmap] + f[nmap]);
if (end)
off.b(end);
}
}
fr = qb.front(), peo = fr;
qb.pop();
for (int i = 4; i > 0; --i)
for (int j = 4; j > 0; --j){
map[i][j] = peo & 1;
peo >>= 1;
}
for (int i = 1; i < 5; ++i)
for (int j = 1; j < 5; ++j){
map[i][j] = ! map[i][j];
if (i - 1 > 0)
map[i - 1][j] = ! map[i - 1][j];
if (j - 1 > 0)
map[i][j - 1] = ! map[i][j - 1];
if (i + 1 < 5)
map[i + 1][j] = ! map[i + 1][j];
if (j + 1 < 5)
map[i][j + 1] = ! map[i][j + 1];
nmap = 0;
for (int k = 1; k < 5; ++k) //{
for (int l = 1; l < 5; ++l){
// cout << map[k][l];
nmap = nmap << 1 | map[k][l];
}
// cout << endl;
// }
// cout << nmap << endl;
map[i][j] = ! map[i][j];
if (i - 1 > 0)
map[i - 1][j] = ! map[i - 1][j];
if (j - 1 > 0)
map[i][j - 1] = ! map[i][j - 1];
if (i + 1 < 5)
map[i + 1][j] = ! map[i + 1][j];
if (j + 1 < 5)
map[i][j + 1] = ! map[i][j + 1];
if (g[nmap] >= 0)
continue;
else{
g[nmap] = g[fr] + 1;
qb.push(nmap);
if (f[nmap] >= 0)
off.b(g[nmap] + f[nmap]);
}
}
fr = qw.front(), peo = fr;
qw.pop();
for (int i = 4; i > 0; --i)
for (int j = 4; j > 0; --j){
map[i][j] = peo & 1;
peo >>= 1;
}
for (int i = 1; i < 5; ++i)
for (int j = 1; j < 5; ++j){
map[i][j] = ! map[i][j];
if (i - 1 > 0)
map[i - 1][j] = ! map[i - 1][j];
if (j - 1 > 0)
map[i][j - 1] = ! map[i][j - 1];
if (i + 1 < 5)
map[i + 1][j] = ! map[i + 1][j];
if (j + 1 < 5)
map[i][j + 1] = ! map[i][j + 1];
nmap = 0;
for (int k = 1; k < 5; ++k) //{
for (int l = 1; l < 5; ++l){
// cout << map[k][l];
nmap = nmap << 1 | map[k][l];
}
// cout << endl;
// }
// cout << nmap << endl;
map[i][j] = ! map[i][j];
if (i - 1 > 0)
map[i - 1][j] = ! map[i - 1][j];
if (j - 1 > 0)
map[i][j - 1] = ! map[i][j - 1];
if (i + 1 < 5)
map[i + 1][j] = ! map[i + 1][j];
if (j + 1 < 5)
map[i][j + 1] = ! map[i][j + 1];
if (h[nmap] >= 0)
continue;
else{
h[nmap] = h[fr] + 1;
qw.push(nmap);
if (f[nmap] >= 0)
off.b(h[nmap] + f[nmap]);
}
}
}
}