Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 状态压缩循环搜索解法

Posted by a280920481 at 2018-12-03 19:00:56 on Problem 2488
```//POJ2488 状态压缩
#include <iostream>
using namespace std;

struct Situ
{
int m;
int nx;
int ny;
int step;
};

const int tx[8] = { -2,-2,-1,-1,1,1,2,2 };
const int ty[8] = { -1,1,-2,2,-2,2,-1,1 };

Situ sta[100];

int staSize;

void mypush(Situ & s);

Situ mypop();

Situ move(Situ & s, int t);

bool test(Situ & s, int t);

void output(int k);

int p, q, ansx[30], ansy[30];

int main()
{
Situ s, s_;
int n, p_q;
bool fin;

cin >> n;

for (int so = 1; so <= n; so++)
{
cin >> p >> q;//每一行的列数 每一列的行数

staSize = 0;
p_q = p * q;
fin = false;

s.m = 1;
s.nx = 0;
s.ny = 0;
s.step = 1;

mypush(s);

while (staSize)
{
s = mypop();

ansx[s.step] = s.nx;
ansy[s.step] = s.ny;

if (s.step == p_q)
{
fin = true;
break;
}

for (int i = 7; i >= 0; i--)
{
if (test(s, i))
{
s_ = move(s, i);

mypush(s_);
}
}
}

if (fin)
{
output(so);
}
else
{
cout << "Scenario #" << so << ":\nimpossible\n\n";
}
}

return 0;
}

void mypush(Situ & s)
{
sta[staSize++] = s;
return;
}

Situ mypop()
{
return sta[--staSize];
}

Situ move(Situ & s, int t)
{
static Situ s_;

s_ = s;
s_.m = s_.m | (1 << (p * (s_.nx + tx[t]) + s_.ny + ty[t]));
s_.nx += tx[t];
s_.ny += ty[t];
s_.step++;

return s_;
}

bool test(Situ & s, int t)
{
if ((s.nx + tx[t] >= 0) && (s.nx + tx[t] < q) && (s.ny + ty[t] >= 0) && (s.ny + ty[t] < p))
{
return !((s.m >> (p * (s.nx + tx[t]) + s.ny + ty[t])) & 1);
}
return false;
}

void output(int k)
{
cout << "Scenario #" << k << ":\n";
for (int i = 1; i <= p * q; i++)
{
cout << (char)(ansx[i] + 65) << ansy[i] + 1;
}
cout << '\n' << '\n';
return;
}
```

Followed by: