Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

双向BFS~0ms,oh yeah!

Posted by 1200017623 at 2013-01-19 18:59:59 on Problem 1077

第一次用双向BFS，要不是不知道那个讨厌的strrev不能用的话就1A了……

具体的标记可以这样实现：
标记栏设为短整型。对于从原始结果正着搜的，在标记时用队列数组下标表示；对于从最终结果逆着搜的，用下标的相反数表示。这样就可以将两路队列不同的搜索结果区分开了。

晒一下代码：（有点长，凑活看吧）
//Single BFS <Memory: 4536K Time: 313ms>
//POJ 1077 Eight
//BFS: mark with sequence number
//DBFS: mark in both way
#include<iostream>
#include<cstring>
#include<cassert>
#define DEST 46233    //The sequence num of "123456780",the destination
using namespace std;
struct Result{
	char status[10];
	short xPos;      //Current position of x
	char move[50];   //record the current searching record! Important
};
Result queue1[25000] = {0},*p1 = queue1,*q1 = queue1 + 1;
Result queue2[25000] = {{"123456780",8,"\0"}},*p2 = queue2,*q2 = queue2 + 1;

char Forward[50] = {0},Backward[50] = {0};
static short used[362881] = {false};    //to mark the searching sequence
//now: the position of q (q1 == queue1 + now1)
int count1 = 1,count2 = 1,now1 = 1,now2 = 1;

int SequenceNum(const Result* m){
	int big[9] = {0},sum = 0;
	for(int i = 0;i < 8;++i){
		for(int j = i + 1;j < 9;++j){
			if(m->status[i] > m->status[j])++big[8-i];
		}
	}
	int fac = 1;
	for(int i = 1;i < 9;++i){
		sum += big[i] * fac;
		fac *= i + 1;
	}
	return sum;
}

void BFS(){
	int step,pos,Snum;
	char temp;
	while(true){

		/* queue1*/

		assert(count1 < 24999);
		pos = p1->xPos;
		step = strlen(p1->move);
		//up
		if(pos > 2){
			strcpy(q1->status,p1->status);
			temp = q1->status[pos];
			q1->status[pos] = q1->status[pos - 3];
			q1->status[pos - 3] = temp;
			q1->xPos = pos - 3;
			Snum = SequenceNum(q1);
			//queue1 is positive queue2 is negative 0 means unsearched
			if(used[Snum] <= 0){   
				strcpy(q1->move,p1->move);
				q1->move[step] = 'u';
				if(used[Snum] < 0){
					strcpy(Forward,q1->move);
					strcpy(Backward,(queue2+(-used[Snum]))->move);
					return;
				}
				else{
					used[Snum] = now1;   //mark a positive number
					++q1,++now1,++count1;
					if(q1 == queue1 + 25000)q1 = queue1+1,now1 = 1;
				}
			}
		}

		//down
		if(pos < 6){
			strcpy(q1->status,p1->status);
			temp = q1->status[pos];
			q1->status[pos] = q1->status[pos + 3];
			q1->status[pos + 3] = temp;
			q1->xPos = pos + 3;
			Snum = SequenceNum(q1);
			//queue1 is positive queue2 is negative 0 means unsearched
			if(used[Snum] <= 0){   
				strcpy(q1->move,p1->move);
				q1->move[step] = 'd';
				if(used[Snum] < 0){
					strcpy(Forward,q1->move);
					strcpy(Backward,(queue2+(-used[Snum]))->move);
					return;
				}
				else{
					used[Snum] = now1;   //mark a positive number
					++q1,++now1,++count1;
					if(q1 == queue1 + 25000)q1 = queue1+1,now1 = 1;
				}
			}
		}

		//left
		if(pos%3 > 0){
			strcpy(q1->status,p1->status);
			temp = q1->status[pos];
			q1->status[pos] = q1->status[pos - 1];
			q1->status[pos - 1] = temp;
			q1->xPos = pos - 1;
			Snum = SequenceNum(q1);
			//queue1 is positive queue2 is negative 0 means unsearched
			if(used[Snum] <= 0){   
				strcpy(q1->move,p1->move);
				q1->move[step] = 'l';
				if(used[Snum] < 0){
					strcpy(Forward,q1->move);
					strcpy(Backward,(queue2+(-used[Snum]))->move);
					return;
				}
				else{
					used[Snum] = now1;   //mark a positive number
					++q1,++now1,++count1;
					if(q1 == queue1 + 25000)q1 = queue1+1,now1 = 1;
				}
			}
		}

		//right
		if(pos%3 < 2){
			strcpy(q1->status,p1->status);
			temp = q1->status[pos];
			q1->status[pos] = q1->status[pos + 1];
			q1->status[pos + 1] = temp;
			q1->xPos = pos + 1;
			Snum = SequenceNum(q1);
			//queue1 is positive queue2 is negative 0 means unsearched
			if(used[Snum] <= 0){   
				strcpy(q1->move,p1->move);
				q1->move[step] = 'r';
				if(used[Snum] < 0){
					strcpy(Forward,q1->move);
					strcpy(Backward,(queue2+(-used[Snum]))->move);
					return;
				}
				else{
					used[Snum] = now1;   //mark a positive number
					++q1,++now1,++count1;
					if(q1 == queue1 + 25000)q1 = queue1+1,now1 = 1;
				}
			}
		}
		//p1 is over
		if(++p1 == queue1 + 25000)p1 = queue1+1;
		--count1;

		/* queue2 */

		assert(count2 < 24999);
		pos = p2->xPos;
		step = strlen(p2->move);
		//up
		if(pos > 2){
			strcpy(q2->status,p2->status);
			temp = q2->status[pos];
			q2->status[pos] = q2->status[pos - 3];
			q2->status[pos - 3] = temp;
			q2->xPos = pos - 3;
			Snum = SequenceNum(q2);
			//queue1 is positive queue2 is negative 0 means unsearched
			if(used[Snum] >= 0){   
				strcpy(q2->move,p2->move);
				q2->move[step] = 'd';  //searching backward,the move is the opposite
				if(used[Snum] > 0){
					strcpy(Forward,(queue1 + used[Snum])->move);
					strcpy(Backward,q2->move);
					return;
				}
				else{
					used[Snum] = -now2;   //mark a negative number
					++q2,++now2,++count2;
					if(q2 == queue2 + 25000)q2 = queue2+1,now2 = 1;
				}
			}
		}

		//down
		if(pos < 6){
			strcpy(q2->status,p2->status);
			temp = q2->status[pos];
			q2->status[pos] = q2->status[pos + 3];
			q2->status[pos + 3] = temp;
			q2->xPos = pos + 3;
			Snum = SequenceNum(q2);
			//queue1 is positive queue2 is negative 0 means unsearched
			if(used[Snum] >= 0){   
				strcpy(q2->move,p2->move);
				q2->move[step] = 'u';
				if(used[Snum] > 0){
					strcpy(Forward,(queue1 + used[Snum])->move);
					strcpy(Backward,q2->move);
					return;
				}
				else{
					used[Snum] = -now2;   //mark a negative number
					++q2,++now2,++count2;
					if(q2 == queue2 + 25000)q2 = queue2+1,now2 = 1;
				}
			}
		}

		//left
		if(pos%3 > 0){
			strcpy(q2->status,p2->status);
			temp = q2->status[pos];
			q2->status[pos] = q2->status[pos - 1];
			q2->status[pos - 1] = temp;
			q2->xPos = pos - 1;
			Snum = SequenceNum(q2);
			//queue1 is positive queue2 is negative 0 means unsearched
			if(used[Snum] >= 0){   
				strcpy(q2->move,p2->move);
				q2->move[step] = 'r';
				if(used[Snum] > 0){
					strcpy(Forward,(queue1+used[Snum])->move); //bug1 detected:q1->queue1
					strcpy(Backward,q2->move);
					return;
				}
				else{
					used[Snum] = -now2;   //mark a negative number
					++q2,++now2,++count2;
					if(q2 == queue2 + 25000)q2 = queue2+1,now2 = 1;
				}
			}
		}

		//right
		if(pos%3 < 2){
			strcpy(q2->status,p2->status);
			temp = q2->status[pos];
			q2->status[pos] = q2->status[pos + 1];
			q2->status[pos + 1] = temp;
			q2->xPos = pos + 1;
			Snum = SequenceNum(q2);
			//queue1 is positive queue2 is negative 0 means unsearched
			if(used[Snum] >= 0){   
				strcpy(q2->move,p2->move);
				q2->move[step] = 'l';
				if(used[Snum] > 0){
					strcpy(Forward,(queue1+used[Snum])->move);
					strcpy(Backward,q2->move);
					return;
				}
				else{
					used[Snum] = -now2;   //bug2 detected: negative number
					++q2,++now2,++count2;
					if(q2 == queue2 + 25000)q2 = queue2+1,now2 = 1;
				}
			}
		}
		//p1 is over
		if(++p2 == queue2 + 25000)p2 = queue2+1;
		--count2;
	}
}

int main(){
	/* Get the original board */
	for(int i = 0;i < 9;++i){
		cin>>p1->status[i];
		if(p1->status[i] == 'x'){
			p1->status[i] = '0';
			p1->xPos = i;
		}
	}
	int reversepair = 0;
	for(int i = 0;i < 8;++i){
		for(int j = i + 1;j < 9;++j){
			if(p1->status[i] == '0' || p1->status[j] == '0')continue;
			if(p1->status[i] < p1->status[j])++reversepair;
		}
	}
	if(reversepair%2){
		printf("unsolvable!\n");
		system("PAUSE");
		return 0;
	}
	if(strcmp(p1->status,"123456780") == 0){
		printf("0\n");
		return 0;
	}
	used[SequenceNum(p1)] = 30000;  //mark first
	used[DEST] = -30000;
	memset(p1->move,0,100*sizeof(char));
	/* Search and print result */
	BFS();
	strrev(Backward);
	printf("%s%s\n",Forward,Backward);
	cin.get();
	cin.get();
	return 0;
}

/*
1 2 3 4 5 6 x 7 8
2 rr
1 2 3 4 8 5 x 7 6
4 rurd
2 3 6 1 5 8 4 7 x
8 uullddrr
 8  6  7  2  5  4  3  x  1
************* Standard Output *****************
49 ruullddrruullddrruullddrruldrulurddlurulddrulurdd
************* My BFS Program puts *****************
31 uulddrruuldldrruuldldrruullddrr correct
************* My DBFS Program puts *****************
31 ruulddruuldldrrullurrdlldruurdd correct

 2  3  4  1  5  x  7  6  8
************* Standard Output *****************
ullddrurdllur druldr
************* My Program puts *****************
ullddrurdllur rdlurd  correct

7 3 8 x 2 6 1 5 4
rrullddrrululdrdlurdr
7 3 6 x 2 8 1 5 4
Assertion failed!   why?
87654321x
ulldruurddluuld druurddluuldrrd  correct

12345687x(Unsolvable)
uulddlurrullddruldrrululdddldldrurullddrurdluurdllurdrd wrong
*/

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> 第一次用双向BFS，要不是不知道那个讨厌的strrev不能用的话就1A了……
> 
> 具体的标记可以这样实现：
> 标记栏设为短整型。对于从原始结果正着搜的，在标记时用队列数组下标表示；对于从最终结果逆着搜的，用下标的相反数表示。这样就可以将两路队列不同的搜索结果区分开了。
> 
> 晒一下代码：（有点长，凑活看吧）
> //Single BFS <Memory: 4536K Time: 313ms>
> //POJ 1077 Eight
> //BFS: mark with sequence number
> //DBFS: mark in both way
> #include<iostream>
> #include<cstring>
> #include<cassert>
> #define DEST 46233    //The sequence num of "123456780",the destination
> using namespace std;
> struct Result{
> 	char status[10];
> 	short xPos;      //Current position of x
> 	char move[50];   //record the current searching record! Important
> };
> Result queue1[25000] = {0},*p1 = queue1,*q1 = queue1 + 1;
> Result queue2[25000] = {{"123456780",8,"\0"}},*p2 = queue2,*q2 = queue2 + 1;
> 
> char Forward[50] = {0},Backward[50] = {0};
> static short used[362881] = {false};    //to mark the searching sequence
> //now: the position of q (q1 == queue1 + now1)
> int count1 = 1,count2 = 1,now1 = 1,now2 = 1;
> 
> int SequenceNum(const Result* m){
> 	int big[9] = {0},sum = 0;
> 	for(int i = 0;i < 8;++i){
> 		for(int j = i + 1;j < 9;++j){
> 			if(m->status[i] > m->status[j])++big[8-i];
> 		}
> 	}
> 	int fac = 1;
> 	for(int i = 1;i < 9;++i){
> 		sum += big[i] * fac;
> 		fac *= i + 1;
> 	}
> 	return sum;
> }
> 
> void BFS(){
> 	int step,pos,Snum;
> 	char temp;
> 	while(true){
> 
> 		/* queue1*/
> 
> 		assert(count1 < 24999);
> 		pos = p1->xPos;
> 		step = strlen(p1->move);
> 		//up
> 		if(pos > 2){
> 			strcpy(q1->status,p1->status);
> 			temp = q1->status[pos];
> 			q1->status[pos] = q1->status[pos - 3];
> 			q1->status[pos - 3] = temp;
> 			q1->xPos = pos - 3;
> 			Snum = SequenceNum(q1);
> 			//queue1 is positive queue2 is negative 0 means unsearched
> 			if(used[Snum] <= 0){   
> 				strcpy(q1->move,p1->move);
> 				q1->move[step] = 'u';
> 				if(used[Snum] < 0){
> 					strcpy(Forward,q1->move);
> 					strcpy(Backward,(queue2+(-used[Snum]))->move);
> 					return;
> 				}
> 				else{
> 					used[Snum] = now1;   //mark a positive number
> 					++q1,++now1,++count1;
> 					if(q1 == queue1 + 25000)q1 = queue1+1,now1 = 1;
> 				}
> 			}
> 		}
> 
> 		//down
> 		if(pos < 6){
> 			strcpy(q1->status,p1->status);
> 			temp = q1->status[pos];
> 			q1->status[pos] = q1->status[pos + 3];
> 			q1->status[pos + 3] = temp;
> 			q1->xPos = pos + 3;
> 			Snum = SequenceNum(q1);
> 			//queue1 is positive queue2 is negative 0 means unsearched
> 			if(used[Snum] <= 0){   
> 				strcpy(q1->move,p1->move);
> 				q1->move[step] = 'd';
> 				if(used[Snum] < 0){
> 					strcpy(Forward,q1->move);
> 					strcpy(Backward,(queue2+(-used[Snum]))->move);
> 					return;
> 				}
> 				else{
> 					used[Snum] = now1;   //mark a positive number
> 					++q1,++now1,++count1;
> 					if(q1 == queue1 + 25000)q1 = queue1+1,now1 = 1;
> 				}
> 			}
> 		}
> 
> 		//left
> 		if(pos%3 > 0){
> 			strcpy(q1->status,p1->status);
> 			temp = q1->status[pos];
> 			q1->status[pos] = q1->status[pos - 1];
> 			q1->status[pos - 1] = temp;
> 			q1->xPos = pos - 1;
> 			Snum = SequenceNum(q1);
> 			//queue1 is positive queue2 is negative 0 means unsearched
> 			if(used[Snum] <= 0){   
> 				strcpy(q1->move,p1->move);
> 				q1->move[step] = 'l';
> 				if(used[Snum] < 0){
> 					strcpy(Forward,q1->move);
> 					strcpy(Backward,(queue2+(-used[Snum]))->move);
> 					return;
> 				}
> 				else{
> 					used[Snum] = now1;   //mark a positive number
> 					++q1,++now1,++count1;
> 					if(q1 == queue1 + 25000)q1 = queue1+1,now1 = 1;
> 				}
> 			}
> 		}
> 
> 		//right
> 		if(pos%3 < 2){
> 			strcpy(q1->status,p1->status);
> 			temp = q1->status[pos];
> 			q1->status[pos] = q1->status[pos + 1];
> 			q1->status[pos + 1] = temp;
> 			q1->xPos = pos + 1;
> 			Snum = SequenceNum(q1);
> 			//queue1 is positive queue2 is negative 0 means unsearched
> 			if(used[Snum] <= 0){   
> 				strcpy(q1->move,p1->move);
> 				q1->move[step] = 'r';
> 				if(used[Snum] < 0){
> 					strcpy(Forward,q1->move);
> 					strcpy(Backward,(queue2+(-used[Snum]))->move);
> 					return;
> 				}
> 				else{
> 					used[Snum] = now1;   //mark a positive number
> 					++q1,++now1,++count1;
> 					if(q1 == queue1 + 25000)q1 = queue1+1,now1 = 1;
> 				}
> 			}
> 		}
> 		//p1 is over
> 		if(++p1 == queue1 + 25000)p1 = queue1+1;
> 		--count1;
> 
> 		/* queue2 */
> 
> 		assert(count2 < 24999);
> 		pos = p2->xPos;
> 		step = strlen(p2->move);
> 		//up
> 		if(pos > 2){
> 			strcpy(q2->status,p2->status);
> 			temp = q2->status[pos];
> 			q2->status[pos] = q2->status[pos - 3];
> 			q2->status[pos - 3] = temp;
> 			q2->xPos = pos - 3;
> 			Snum = SequenceNum(q2);
> 			//queue1 is positive queue2 is negative 0 means unsearched
> 			if(used[Snum] >= 0){   
> 				strcpy(q2->move,p2->move);
> 				q2->move[step] = 'd';  //searching backward,the move is the opposite
> 				if(used[Snum] > 0){
> 					strcpy(Forward,(queue1 + used[Snum])->move);
> 					strcpy(Backward,q2->move);
> 					return;
> 				}
> 				else{
> 					used[Snum] = -now2;   //mark a negative number
> 					++q2,++now2,++count2;
> 					if(q2 == queue2 + 25000)q2 = queue2+1,now2 = 1;
> 				}
> 			}
> 		}
> 
> 		//down
> 		if(pos < 6){
> 			strcpy(q2->status,p2->status);
> 			temp = q2->status[pos];
> 			q2->status[pos] = q2->status[pos + 3];
> 			q2->status[pos + 3] = temp;
> 			q2->xPos = pos + 3;
> 			Snum = SequenceNum(q2);
> 			//queue1 is positive queue2 is negative 0 means unsearched
> 			if(used[Snum] >= 0){   
> 				strcpy(q2->move,p2->move);
> 				q2->move[step] = 'u';
> 				if(used[Snum] > 0){
> 					strcpy(Forward,(queue1 + used[Snum])->move);
> 					strcpy(Backward,q2->move);
> 					return;
> 				}
> 				else{
> 					used[Snum] = -now2;   //mark a negative number
> 					++q2,++now2,++count2;
> 					if(q2 == queue2 + 25000)q2 = queue2+1,now2 = 1;
> 				}
> 			}
> 		}
> 
> 		//left
> 		if(pos%3 > 0){
> 			strcpy(q2->status,p2->status);
> 			temp = q2->status[pos];
> 			q2->status[pos] = q2->status[pos - 1];
> 			q2->status[pos - 1] = temp;
> 			q2->xPos = pos - 1;
> 			Snum = SequenceNum(q2);
> 			//queue1 is positive queue2 is negative 0 means unsearched
> 			if(used[Snum] >= 0){   
> 				strcpy(q2->move,p2->move);
> 				q2->move[step] = 'r';
> 				if(used[Snum] > 0){
> 					strcpy(Forward,(queue1+used[Snum])->move); //bug1 detected:q1->queue1
> 					strcpy(Backward,q2->move);
> 					return;
> 				}
> 				else{
> 					used[Snum] = -now2;   //mark a negative number
> 					++q2,++now2,++count2;
> 					if(q2 == queue2 + 25000)q2 = queue2+1,now2 = 1;
> 				}
> 			}
> 		}
> 
> 		//right
> 		if(pos%3 < 2){
> 			strcpy(q2->status,p2->status);
> 			temp = q2->status[pos];
> 			q2->status[pos] = q2->status[pos + 1];
> 			q2->status[pos + 1] = temp;
> 			q2->xPos = pos + 1;
> 			Snum = SequenceNum(q2);
> 			//queue1 is positive queue2 is negative 0 means unsearched
> 			if(used[Snum] >= 0){   
> 				strcpy(q2->move,p2->move);
> 				q2->move[step] = 'l';
> 				if(used[Snum] > 0){
> 					strcpy(Forward,(queue1+used[Snum])->move);
> 					strcpy(Backward,q2->move);
> 					return;
> 				}
> 				else{
> 					used[Snum] = -now2;   //bug2 detected: negative number
> 					++q2,++now2,++count2;
> 					if(q2 == queue2 + 25000)q2 = queue2+1,now2 = 1;
> 				}
> 			}
> 		}
> 		//p1 is over
> 		if(++p2 == queue2 + 25000)p2 = queue2+1;
> 		--count2;
> 	}
> }
> 
> int main(){
> 	/* Get the original board */
> 	for(int i = 0;i < 9;++i){
> 		cin>>p1->status[i];
> 		if(p1->status[i] == 'x'){
> 			p1->status[i] = '0';
> 			p1->xPos = i;
> 		}
> 	}
> 	int reversepair = 0;
> 	for(int i = 0;i < 8;++i){
> 		for(int j = i + 1;j < 9;++j){
> 			if(p1->status[i] == '0' || p1->status[j] == '0')continue;
> 			if(p1->status[i] < p1->status[j])++reversepair;
> 		}
> 	}
> 	if(reversepair%2){
> 		printf("unsolvable!\n");
> 		system("PAUSE");
> 		return 0;
> 	}
> 	if(strcmp(p1->status,"123456780") == 0){
> 		printf("0\n");
> 		return 0;
> 	}
> 	used[SequenceNum(p1)] = 30000;  //mark first
> 	used[DEST] = -30000;
> 	memset(p1->move,0,100*sizeof(char));
> 	/* Search and print result */
> 	BFS();
> 	strrev(Backward);
> 	printf("%s%s\n",Forward,Backward);
> 	cin.get();
> 	cin.get();
> 	return 0;
> }
> 
> /*
> 1 2 3 4 5 6 x 7 8
> 2 rr
> 1 2 3 4 8 5 x 7 6
> 4 rurd
> 2 3 6 1 5 8 4 7 x
> 8 uullddrr
>  8  6  7  2  5  4  3  x  1
> ************* Standard Output *****************
> 49 ruullddrruullddrruullddrruldrulurddlurulddrulurdd
> ************* My BFS Program puts *****************
> 31 uulddrruuldldrruuldldrruullddrr correct
> ************* My DBFS Program puts *****************
> 31 ruulddruuldldrrullurrdlldruurdd correct
> 
>  2  3  4  1  5  x  7  6  8
> ************* Standard Output *****************
> ullddrurdllur druldr
> ************* My Program puts *****************
> ullddrurdllur rdlurd  correct
> 
> 7 3 8 x 2 6 1 5 4
> rrullddrrululdrdlurdr
> 7 3 6 x 2 8 1 5 4
> Assertion failed!   why?
> 87654321x
> ulldruurddluuld druurddluuldrrd  correct
> 
> 12345687x(Unsolvable)
> uulddlurrullddruldrrululdddldldrurullddrurdluurdllurdrd wrong
> */
> 
>

Home Page Go Back To top