Class & Homework - BFS

Catch That Cow // poj 3278

一个样例程序，速度一般，但思路清晰

#include <iostream> 
#include <cstring> 
#include <queue>
using namespace std;
const int MAXN=100000;
int visited[MAXN+2]; //访问过的地址
struct Step{
	int x; //坐标
	int s; //已经走了多少步
	Step(int x_,int s_):x(x_),s(s_){} 
}; 
queue<Step> q;

int main(){
	int N,K; 
	scanf("%d %d",&N,&K);
	memset(visited,0,sizeof(visited));
	q.push(Step(N,0)); visited[N]=1; //初始化 
	while(!q.empty()){
		Step t=q.front();
		if(t.x==K){
			printf("%d\n",t.s);
			break;
		}
		else{
			if(t.x-1>=0&&!visited[t.x-1]){
				q.push(Step(t.x-1,t.s+1));
				visited[t.x-1]=1;
			}
			if(t.x+1<=MAXN&&!visited[t.x+1]){
				q.push(Step(t.x+1,t.s+1));
				visited[t.x+1]=1;
			}
			if(2*t.x<=MAXN&&!visited[2*t.x]){
				q.push(Step(2*t.x,t.s+1));
				visited[2*t.x]=1;
			}
			q.pop();
		}
	}
	return 0;
}

EIGHT // poj 1077，八数码问题

郭老师给的例程，最简单做法，poj  437ms，但在HDOJ上会TLE

#include <iostream>
#include <bitset>
#include <cstring>
using namespace std;
int goalStatus; //目标状态
bitset<362880> Flags; //节点是否扩展的标记
const int MAXS = 400000; //>400000
char result[MAXS]; //结果
struct Node {
	int status; //状态, 即排列的编号
	int father; //父节点指针
	char move; //父节点到本节点的移动方式u/d/r/l
	Node(int s, int f, char m):status(s), father(f), move(m) { }
	Node() { }
};
Node myQueue[MAXS]; //状态队列, 状态总数362880
int qHead;
int qTail;
//队头指针和队尾指针
char sz4Moves[] = "udrl"; //四种动作
unsigned int factorial[21];
//存放0-20的阶乘. 21的阶乘unsigned放不下了

//给定排列, 求序号
unsigned int GetPermutationNumForInt(int * perInt, int len){
//perInt里放着整数0到(len-1)的一个排列, 求它是第几个排列
//len不能超过21
	unsigned int num = 0;
	bool used[21];
	memset(used, 0, sizeof(bool)*len);
	for( int i = 0; i < len; ++ i ) {
		unsigned int n = 0;
		for( int j = 0; j < perInt[i]; ++ j) {
			if( !used[j] ) ++n;
		}
		num += n * factorial[len-i-1];
		used[perInt[i]] = true;
	}
	return num;
}

//给定排列,求序号
template< class T>
unsigned int GetPermutationNum( T s1, T s2, int len ){
//[s1,s1+len)里面放着第0号排列,[s2,s2+len)是要求序号的排列
//两者必须一样长, len不能超过21
//排列的每个元素都不一样. 返回排列的编号
	int perInt[21]; //要转换成[0, len-1] 的整数的排列
	for( int i = 0; i < len; ++i )
	for( int j = 0; j < len; ++j ) {
		if( * ( s2 + i ) == * ( s1 + j )) {
			perInt[i] = j;
			break;
		}
	}
	unsigned int num = GetPermutationNumForInt(perInt, len);
	return num;
}

template <class T>
void GenPermutationByNum(T s1, T s2, int len, unsigned int No)
//根据排列编号,生成排列
{ //[s1,s1+len) 里面放着第0号permutation,排列的每个元素都不一样
	int perInt[21]; //要转换成[0,len-1] 的整数的排列
	bool used[21];
	memset(used, 0, sizeof(bool)*len);
	for(int i = 0; i < len; ++ i ) {
		int j;
		for( j = 0; j < len; ++j ) {
			if( !used[j] ) {
				if( factorial[len - i - 1] >= No+1) break;
				else No -= factorial[len - i - 1];
			}
		}
		perInt[i] = j;
		used[j] = true;
	}
	for( int i = 0;i < len; ++i )
		* ( s2 + i ) = * ( s1 + perInt[i]);
}

//字符串形式的状态, 转换为整数形式的状态(排列序号）
int StrStatusToIntStatus( const char * strStatus){
	return GetPermutationNum( "012345678", strStatus, 9);
}
//整数形式的状态(排列序号）, 转换为字符串形式的状态
void IntStatusToStrStatus( int n, char * strStatus){
	GenPermutationByNum((char*)"012345678", strStatus, 9, n);
}

int NewStatus( int nStatus, char cMove) {
//求从nStatus经过cMove 移动后得到的新状态. 若移动不可行则返回-1
	char szTmp[20]; int nZeroPos;
	IntStatusToStrStatus(nStatus, szTmp);
	for( int i = 0;i < 9; ++ i )
		if( szTmp[i] == '0' ) {
			nZeroPos = i;
			break;
		} //返回空格的位置
	switch( cMove) {
		case 'u': if( nZeroPos - 3 < 0 ) return -1; //空格在第一行
				else { szTmp[nZeroPos] = szTmp[nZeroPos - 3];
				szTmp[nZeroPos - 3] = '0'; }
				break;
		case 'd': if( nZeroPos + 3 > 8 ) return -1; //空格在第三行
				else { szTmp[nZeroPos] = szTmp[nZeroPos + 3];
				szTmp[nZeroPos + 3] = '0'; }
				break;
		case 'l': if( nZeroPos % 3 == 0) return -1;
		//空格在第一列
				else { szTmp[nZeroPos] = szTmp[nZeroPos -1];
				szTmp[nZeroPos -1 ] = '0'; }
				break;
		case 'r': if( nZeroPos % 3 == 2) return -1;
		//空格在第三列
				else { szTmp[nZeroPos] = szTmp[nZeroPos + 1];
				szTmp[nZeroPos + 1 ] = '0'; }
				break;
	}
	return StrStatusToIntStatus(szTmp);
}

bool Bfs(int nStatus) { //寻找从初始状态nStatus到目标的路径
	int nNewStatus; Flags.reset(); //清除所有扩展标记
	qHead = 0; qTail = 1;
	myQueue[qHead] = Node(nStatus, -1, 0);
	while ( qHead != qTail) { //队列不为空
		nStatus = myQueue[qHead].status;
		if( nStatus == goalStatus ) //找到目标状态
		return true;
		for( int i = 0;i < 4;i ++ ) { //尝试4种移动
			nNewStatus = NewStatus(nStatus, sz4Moves[i]);
			if( nNewStatus == -1 ) continue; //不可移, 试下一种
			if( Flags[nNewStatus]) continue; //扩展标记已经存在, 则不入队
			Flags.set(nNewStatus, true); //设上已扩展标记
			myQueue[qTail++] = Node(nNewStatus, qHead, sz4Moves[i]);
			//新节点入队列
		}
		qHead ++;
	}
	return false;
}

int main(){
	factorial[0] = factorial[1] =1;
	for(int i = 2;i < 21; ++i )
	factorial[i] = i * factorial[i-1];
	goalStatus = StrStatusToIntStatus("123456780");
	char szLine[50];
	char szLine2[20];
	while( cin.getline(szLine, 48)) {
		int i, j;
		//将输入的原始字符串变为数字字符串
		for( i = 0, j = 0; szLine[i]; i ++ ) {
			if( szLine[i] != ' ' ) {
				if( szLine[i] == 'x' ) szLine2[j++] = '0';
				else szLine2[j++] = szLine[i];
			}
		}
		szLine2[j] = 0; //字符串形式的初始状态
		int sumGoal = 0; //从此往后用奇偶性判断是否有解
		for( int i = 0; i < 8; ++i )
		sumGoal += i-1;
		int sumOri = 0;
		for( int i = 0; i < 9; ++i ) {
			if( szLine2[i] == '0')
			continue;
			for( int j = 0; j < i; ++j ) {
				if( szLine2[j] < szLine2[i] && szLine2[j] != '0' )
				sumOri ++;
			}
		}
		if( sumOri %2 != sumGoal %2 ) {
			cout << "unsolvable" << endl;
			continue;
		}
		//上面用奇偶性判断是否有解
		if( Bfs(StrStatusToIntStatus(szLine2))) {
			int nMoves = 0;
			int nPos = qHead;
			do { //通过father找到成功的状态序列, 输出相应步骤
				result[nMoves++] = myQueue[nPos].move;
				nPos = myQueue[nPos].father;
			} while( nPos ); //nPos = 0 说明已经回退到初始状态了
			for( int i = nMoves -1; i >= 0; i -- )
			cout << result[i];
		}
		else
		cout << "unsolvable" << endl;
	}
}

Flip Game // oj 1753

第一次写还是遇上了一点挑战，主要是怎样存储数据。棋盘的结构相当好，16个格子，用 short 刚好能表示。

所以，改用位运算后，哪怕不剪枝都能过。

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
bool board[4][4];
struct Board{
	short b;
	short visited;
	short step;
	Board():b(0),visited(0),step(0){
		for(int i=0;i<4;++i) for(int j=0;j<4;++j) b^=board[i][j]<<(15-4*i-j);
	}
};
void flip(int i,int j,Board&p){
	p.b^=1<<(15-4*i-j);
	if(i>0) p.b^=1<<(19-4*i-j);
	if(j>0) p.b^=1<<(16-4*i-j);
	if(i<3) p.b^=1<<(11-4*i-j);
	if(j<3) p.b^=1<<(14-4*i-j);
}
bool check(const Board&p){
	return p.b==0 || p.b==short(~0);
}
queue<Board> q;

int main(){
	for(int i=0;i<4;++i) for(int j=0;j<4;++j){
		char c; scanf("%c",&c);
		board[i][j]= (c=='b')?1:0;
		if(j==3) scanf("%c",&c);
	} 
	q.push(Board());
	while(!q.empty()){
		Board t=q.front();
		if(check(t)){
			printf("%d\n",t.step); 
			return 0;
		}
		for(int i=0;i<4;++i) for(int j=0;j<4;++j){
			if(!((t.visited>>(15-4*i-j))&&1)){
				Board tt=t;
				tt.visited^=1<<(15-4*i-j);
				flip(i,j,tt);
				++tt.step;
				q.push(tt);
			}
		}
		q.pop();
	}
	printf("Impossible\n");
}

迷宫问题 // oj 4127

算是第一次自己写路径记忆，需要明确，last 最好是 node*，因为如果记录它在store中的位置，同一节点不同路径就不好说了。另外的问题在于，既然使用指针，这些结点都要存起来，那么 last 应对应它在 store 中的位置。

【待优化】

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
bool maze[5][5];
bool visited[5][5];
struct node{
	int i,j;
	int pos; //在store中的位置
	node*last;
	node(){}
	node(int i_,int j_,int p,node*l):i(i_),j(j_),pos(p),last(l){} 
}store[101];
int pos=0;
queue<node> q;

int main(){
	for(int i=0;i<5;++i) for(int j=0;j<5;++j) scanf("%d",maze[i]+j);
	node t(0,0,0,NULL);
	visited[0][0]=1;
	q.push(t); store[pos++]=t;
	while(!q.empty()){
		node t=q.front();
		int p=t.pos;
		if(t.i==4&&t.j==4){
			vector<node*> out;
			node *l = &t;
			int cnt=0;
			while(l!=NULL){
				out.push_back(l);
				++cnt;
				l=l->last;
			}
			for(int k=cnt-1;k>=0;--k) printf("(%d, %d)\n",out[k]->i,out[k]->j);
			return 0;
		}
		if(t.i<4&&maze[t.i+1][t.j]==0&&!visited[t.i+1][t.j]){
			q.push(node(t.i+1,t.j,pos,store+p));
			store[pos++]=node(t.i+1,t.j,pos,store+p);
			visited[t.i+1][t.j]=1;
		}
		if(t.j<4&&maze[t.i][t.j+1]==0&&!visited[t.i][t.j+1]){
			q.push(node(t.i,t.j+1,pos,store+p));
			store[pos++]=node(t.i,t.j+1,pos,store+p);
			visited[t.i][t.j+1]=1;
		}
		q.pop();
	}
}