首页 > 代码库 > POJ 2965-The Pilots Brothers' refrigerator--位运算+BFS+回溯路径

POJ 2965-The Pilots Brothers' refrigerator--位运算+BFS+回溯路径

2024-07-17 13:38:06   229人阅读

The Pilots Brothers‘ refrigerator
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 18576 Accepted: 7108 Special Judge

Description

The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.

There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.

The task is to determine the minimum number of handle switching necessary to open the refrigerator.

Input

The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “?” means “open”. At least one of the handles is initially closed.

Output

The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.

Sample Input

-+--
----
----
-+--

Sample Output

6
1 1
1 3
1 4
4 1
4 3
4 4

Source

Northeastern Europe 2004, Western Subregion
和上一个位运算的差不多，但这个要需要提前把16种操作存起来（这样还跑了400多MS） 多了一个回溯路径，很好办，依然是在结构体中加一个pre变量来标记队列下标（一开始队列开小了 调了一上午没找到错。。sad 以后还是要习惯使用STL队列）
可能很多人会看不懂怎么提前把16种状态存起来 很简单，（我也是想了一晚上） 对于任意一个位置，因为我们要枚举16个位置来改变状态，假设在第1行第1列（下标均从0开始） 我们现在要改变 （1,1） 这个位置的门的状态，此时i=5（用的一维字符数组），我们要用当前状态s   s^=(1^5^9^13^4^6^7) 即（1,1）所在的行和列的所有元素 然后分别计算16个位置的状态存在一个数组里就可以了

 
#include <cstdio>//BFS
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
char ma[20];
bool vis[70000];
int dir[16]={4383,8751,17487,34959,4593,8946,17652,35064,7953,12066,20292,36744,61713,61986,62532,63624};
typedef struct node
{
  int x,y,state,pre,step;
};
node que[500100];
int s,e,ansx[100100],ansy[100100];
void bfs(int sta)
{
	s=0;e=0;
	node t,v;int pos,i;
	t.pre=0;t.state=sta;t.step=0;
	que[e++]=t;
	while(s<e)
	{
		v=que[s];pos=s;s++;
		if(v.state==0)
		{
			cout<<v.step<<endl;
			int te=pos,p=0;
			for(i=0;i<v.step;i++)//回溯路径
			{
				ansx[p]=que[te].x;ansy[p]=que[te].y;
				te=que[te].pre;p++;
			}
			for(i=p-1;i>=0;i--)
				cout<<ansx[i]<<" "<<ansy[i]<<endl;
			return ;
		}
		for(i=0;i<16;i++)
		{
			node tem=v;
			tem.state^=dir[i];
			if(!vis[tem.state])
			{
				vis[tem.state]=1;
				tem.pre=pos;
				tem.x=i/4+1;tem.y=i%4+1;
				tem.step++;
				que[e++]=tem;
			}
		}
	}
}
int main()
{
	memset(vis,0,sizeof(vis));
	int i=0,sum=0;
	while(i<16)
	{
		cin>>ma[i];
		if(ma[i]=='+')
			sum+=1<<i;
		++i;
	}
	bfs(sum);
    return 0;
}


联系
我们