一、深度优先搜索

二、广度优先搜索

1、Wikioi 1004 四子连棋

在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

●	○	●
○	●	○	●
●	○	●	○
○	●	○

 

从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。

用最少的步数移动到目标棋局的步数。

BWBO
WBWB
BWBW
WBWO

5

这是一道很经典的广搜题，需要运用判重的知识，广搜过程应该很好理解，就是每次取出队首的状态，在队首的状态棋盘中找到两个空格，并将空格和相邻的棋子交换，要注意这里有先手和后手之分，BFS的状态应该包含棋盘、搜索步数、哈希值和最近下的棋的颜色，最近下的是白色，那么空格只能和黑棋交换，否则空格只能和白棋交换。判重也是一样，对于状态(s,最后下的是黑棋)和(s,最后下的是白棋)两种状态来说，虽然棋盘数组是一样的，但是最后下的棋颜色不同，最终的结果也会不同，因此判重数组应该是两维的：第一维是棋盘的哈希值，第二维是棋盘的最后下的棋的颜色，另外要注意，如果用三进制表示棋盘的哈希值，棋盘的哈希值<=3^16，这个范围明显超出了int表达范围，因此需要用Map容器保存棋盘哈希值这一个维度，也可以用string类型保存这个哈希值，或许会简单很多，但是要牺牲一点空间，如果想要空间不要时间，也可以用康托展开去保存哈希值，写起来复杂很多。

#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>#include <map>#define MAXQ 100000#define MAXN 1000000using namespace std;map<int,bool>inQueue[4];struct node{	int step; //移动步数(BFS深度)	int hash; //棋盘哈希值(三进制转十进制后的数)	int map[6][6];	int last; //最后一次下棋的是白还是黑，last=1表示黑，last=2表示白}first,q[MAXQ];int h=0,t=1;//bool inQueue[MAXN][4]; //inQueue[s][1]表示黑子最后下，状态为s的情况在队列里，inQueue[s][2]表示白字最后下，状态为s的情况在队列里int xx[]={1,-1,0,0},yy[]={0,0,1,-1};int getHashFromArray(node status) //获取棋盘状态的哈希值{	int sum=0;	for(int i=1;i<=4;i++)		for(int j=1;j<=4;j++)		{			sum*=3;			sum+=status.map[i][j];		}	return sum;}bool check(node status) //检查状态status是否符合要求{	int flag=0;	for(int i=1;i<=4;i++)	{		int j;		for(j=2;j<=4;j++)			if(status.map[i][j]!=status.map[i][j-1])				break;		if(j>4) return true;	}	for(int j=1;j<=4;j++)	{		int i;		for(i=2;i<=4;i++)			if(status.map[i][j]!=status.map[i-1][j])				break;		if(i>4) return true;	}	if(status.map[1][1]==status.map[2][2]&&status.map[2][2]==status.map[3][3]&&status.map[3][3]==status.map[4][4])		return true;	if(status.map[1][4]==status.map[2][3]&&status.map[2][3]==status.map[3][2]&&status.map[3][2]==status.map[4][1])		return true;    return false;}bool inMap(int x,int y){	if(x<0||x>4||y<0||y>4) return false;	return true;}int bfs(){	//Case1:先手黑棋	first.step=0;	first.last=1;	first.hash=getHashFromArray(first); //获取初始棋盘的哈希值	q[h]=first;	inQueue[first.last][first.hash]=true;	//Case2:先手白棋	first.last=2;	q[t++]=first;	inQueue[first.last][first.hash]=true;	//BFS过程	while(h<t)	{		node now=q[h++]; //队首出列		inQueue[now.last][now.hash]=false;		if(check(now)) //符合题目的目标要求，则返回答案			return now.step;		for(int x=1;x<=4;x++) //寻找空格坐标(x,y)			for(int y=1;y<=4;y++)			{				if(now.map[x][y]) continue;				for(int dir=0;dir<4;dir++) //四个方向移动空格				{					int newx=x+xx[dir],newy=y+yy[dir];					if(!inMap(newx,newy)) continue; //越界了					if(now.map[newx][newy]==now.last) //(newx,newy)的颜色和最近下的棋子颜色一样，不能让空格往这移动，黑白棋要轮流下						continue;					node next=now;					next.step++;					next.last=3-next.last; //这一局下的棋和上一局颜色相反					swap(next.map[x][y],next.map[newx][newy]);					next.hash=getHashFromArray(next);					if(!inQueue[next.last][next.hash]) //该状态没有被访问过					{						q[t++]=next;						inQueue[next.last][next.hash]=true;					}				}			}	}}int main(){	char s[10];	for(int i=1;i<=4;i++)	{		scanf("%s",s+1);		for(int j=1;j<=4;j++)		{			if(s[j]=='B') first.map[i][j]=1;			else if(s[j]=='W') first.map[i][j]=2;		}	}	printf("%d\n",bfs());	return 0;}

[NOIP 2014复习]第二章：搜索