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

写死我了,总算水过去了,贴个代码留念!

Posted by nan5515522 at 2014-04-27 09:13:16 on Problem 2965
#include<iostream>
#include<Cstdio>
#include<Cstring>
#include<stack>
using namespace std;


struct Node
{
	int x, step;
	int prev, a1, a2;

};

int mark[65536], n;
int p[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192,
	16384, 32768, 65536, 131072};

Node q[65536];

int bfs()
{
	Node cur, next, temp1;
	int front = 0, end = 1;
	int temp;
	if(n == 0)
		return 0;
	
	cur.x = n;
	cur.step = 0;
	q[front] = cur;
	mark[n] = 1;
	
	while(front <= end)
	{
		cur = q[front++];
		for(int i = 0; i < 16; ++i)
		{
			next.x = cur.x;
			next.x = cur.x ^ p[i];
			
			next.a1 = i / 4 + 1;
			next.a2 = i % 4 + 1;
			next.prev = front - 1;
			

			temp = i + 4;
			while(temp < 16)
			{
				next.x ^= p[temp];
				temp += 4;
			}
			
			temp = i - 4;
			while(temp >= 0)
			{
				next.x ^= p[temp];
				temp -= 4;
			}
			
			temp = i;
			if(temp % 4 < 3)
			{
				temp ++;
			   while(1)
			   {
				   if(temp % 4 == 3)
					   break;
				   next.x ^= p[temp];
				   temp ++;
			   }
				next.x ^= p[temp];
			}
			
			temp = i;
			if(temp % 4 > 0)
			{
				temp --;
				while(1)
				{
					if(temp % 4 == 0)
						break;
					next.x ^= p[temp];
					temp --;
					
				}
				next.x ^= p[temp];
			}
			
			if(next.x == 0)
			{
				printf("%d\n",cur.step + 1);
				temp1 = next;
				next.step = cur.step + 1;
				q[end] = next;
				stack<int> st;
				st.push(end);
				
				while (1)
				{
					//cout << temp1.a1 << " " << temp1.a2 << endl;
					if(q[temp1.prev].step != 0)
					{
					   st.push(temp1.prev);
					   temp1 = q[temp1.prev];
					}
					
					if(q[temp1.prev].step == 0)
						break;
				}
				
				while (!st.empty())
				{
					int pop1 = st.top();
					st.pop();
					cout << q[pop1].a1 << " " << q[pop1].a2 << endl;
				}
				return cur.step + 1;
			}
			
			if(mark[next.x] != 1)
			{
				next.step = cur.step + 1;
				mark[next.x] = 1;
				q[end++] = next;
			}
		}
	}
	return -1;
}





int main()
{
	int i, j, temp;
	char c;
	n = 0;
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 4; j++)
		{
			scanf("%c", &c);
			temp = i * 4 + j;
			if(c=='+')
				n = n + (1 << temp);
			
		}
		getchar();
	}
	
	bfs();	
	return 0;}

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