POJ 2965:非算法优化的重要:时间直减 50%!
可以说这道题和 POJ 1753 特别相似,唯一不同的是,这道题改变了翻转方法,如果直接位运算 + BFS,会稍微有一点点超时。 所以,这次我采用了非算法方面的优化,直接通过下面的方法将题目的时间减少了50%:
- 用宏彻底消除了几乎所有函数的调用开支。
- 使用非同步读写优化读写速度(见代码注释)。
/*
* Flip Game (POJ 2965)
* URL: http://poj.org/problem?id=2965
* Author: Ceeji Cheng
* Type: 枚举 + 位运算
* Status: Sovled
* Visit http://ceeji.net/ for more information.
* 2010-11-14
*
*/
#include <iostream>
#include <cstring>
#define count 16
#define rwcount 4
#define bitwidth 16
#define maxlength 65538
#define copyarr(source,dest) dest = source;
#define flip(pstatus, x, y) \
for (unsigned int ii = 0; ii < rwcount; ii += 1) \
{ \
pstatus = pstatus ^ (1 << (bitwidth - (x * rwcount + ii) - 1)); \
} \
for (unsigned int ii = 0; ii < rwcount; ii += 1) \
{ \
pstatus = pstatus ^ (1 << (bitwidth - (ii * rwcount + y) - 1)); \
} \
pstatus = pstatus ^ (1 << (bitwidth - (x * rwcount + y) - 1));
#define output(steps) \
cout << steps;
#define check(pstatus) (pstatus == 0)
#define hassame(status) used[status]
typedef unsigned short round_status;
typedef unsigned int uint;
using namespace std;
bool used[maxlength];
void init(round_status &pstatus)
{
std::ios::sync_with_stdio(false); // 优化读入速度。
memset(used, 0, sizeof(used));
pstatus = 0;
char c;
for (uint i = 0; i < count; ++i)
{
do
{
cin >> c;
}
while (!(c == '-' || c == '+'));
if (c == '+')
pstatus = pstatus | (1 << (15 - i));
}
}
void output_detail(int p, round_status (&status)[maxlength], int (&cx)[maxlength], int (&cy)[maxlength], int (&father)[maxlength])
{
if (p <= 0)
return;
output_detail(father[p], status, cx, cy, father);
cout << cx[p] + 1 << ' ' << cy[p] + 1 << endl;
}
/* Find the result. */
void search(round_status &pstatus)
{
round_status status[maxlength];
int step[maxlength], father[maxlength], cx[maxlength], cy[maxlength];
int pf = 0, pc = 1;
step[0] = 0;
cx[0] = -1;
cy[0] = -1;
status[0] = pstatus;
father[0] = 0;
used[pstatus] = true;
do
{
for (uint i = 0; i < rwcount; ++i)
{
for (uint j = 0; j < rwcount; ++j)
{
status[pc] = status[pf];
flip(status[pc], i, j);
if (hassame(status[pc]))
{
continue;
}
step[pc] = step[pf] + 1;
used[status[pc]] = true;
father[pc] = pf;
cx[pc] = i;
cy[pc] = j;
if (check(status[pc]))
{
output(step[pf] + 1);
cout << endl;
output_detail(pc, status, cx, cy, father);
return;
}
++pc;
if (pc > maxlength - 1)
{
cout << "Impossible";
return;
}
}
}
++pf;
}
while ((pf < pc));
cout << "Impossible";
return;
}
int main(void)
{
round_status start_status; // start status of the field.
init(start_status);
if (check(start_status))
{
output(0);
return 0;
}
search(start_status);
return 0;
}
题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名。
© 转载需附带本文链接,依据 CC BY-NC-SA 4.0 发布。