Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

状态压缩循环搜索解法

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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator