程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [NOIP 2014復習]第二章：搜索

[NOIP 2014復習]第二章：搜索

編輯：C++入門知識

[NOIP 2014復習]第二章：搜索

一、深度優先搜索

二、廣度優先搜索

1、Wikioi 1004 四子連棋

題目描述 Description

在一個4*4的棋盤上擺放了14顆棋子，其中有7顆白色棋子，7顆黑色棋子，有兩個空白地帶，任何一顆黑白棋子都可以向上下左右四個方向移動到相鄰的空格，這叫行棋一步，黑白雙方交替走棋，任意一方可以先走，如果某個時刻使得任意一種顏色的棋子形成四個一線（包括斜線），這樣的狀態為目標棋局。
● ○ ● ○ ● ○ ● ● ○ ● ○ ○ ● ○

輸入描述 Input Description

從文件中讀入一個4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地帶用O表示。

輸出描述 Output Description

用最少的步數移動到目標棋局的步數。

樣例輸入 Sample Input

BWBO
WBWB
BWBW
WBWO

樣例輸出 Sample Output

5

這是一道很經典的廣搜題，需要運用判重的知識，廣搜過程應該很好理解，就是每次取出隊首的狀態，在隊首的狀態棋盤中找到兩個空格，並將空格和相鄰的棋子交換，要注意這裡有先手和後手之分，BFS的狀態應該包含棋盤、搜索步數、哈希值和最近下的棋的顏色，最近下的是白色，那麼空格只能和黑棋交換，否則空格只能和白棋交換。判重也是一樣，對於狀態(s,最後下的是黑棋)和(s,最後下的是白棋)兩種狀態來說，雖然棋盤數組是一樣的，但是最後下的棋顏色不同，最終的結果也會不同，因此判重數組應該是兩維的：第一維是棋盤的哈希值，第二維是棋盤的最後下的棋的顏色，另外要注意，如果用三進制表示棋盤的哈希值，棋盤的哈希值<=3^16，這個范圍明顯超出了int表達范圍，因此需要用Map容器保存棋盤哈希值這一個維度，也可以用string類型保存這個哈希值，或許會簡單很多，但是要犧牲一點空間，如果想要空間不要時間，也可以用康托展開去保存哈希值，寫起來復雜很多。

#include 
#include 
#include 
#include 
#include 

#define MAXQ 100000
#define MAXN 1000000

using namespace std;

mapinQueue[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
2、Wikioi 1026 逃跑的拉爾夫
題目描述 Description 

年輕的拉爾夫開玩笑地從一個小鎮上偷走了一輛車，但他沒想到的是那輛車屬於警察局，並且車上裝有用於發射車子移動路線的裝置。
那個裝置太舊了，以至於只能發射關於那輛車的移動路線的方向信息。
編寫程序，通過使用一張小鎮的地圖幫助警察局找到那輛車。程序必須能表示出該車最終所有可能的位置。
小鎮的地圖是矩形的，上面的符號用來標明哪兒可以行車哪兒不行。“.”表示小鎮上那塊地方是可以行車的，而符號“X”表示此處不能行車。拉爾夫所開小車的初始位置用字符的“*”表示，且汽車能從初始位置通過。
汽車能向四個方向移動：向北(向上)，向南(向下)，向西(向左)，向東(向右)。
拉爾夫所開小車的行動路線是通過一組給定的方向來描述的。在每個給定的方向，拉爾夫駕駛小車通過小鎮上一個或更多的可行車地點。


輸入描述 Input Description 


輸入文件的第一行包含兩個用空格隔開的自然數R和C，1≤R≤50，1≤C≤50，分別表示小鎮地圖中的行數和列數。
以下的R行中每行都包含一組C個符號(“.”或“X”或“*”)用來描述地圖上相應的部位。
接下來的第R+2行包含一個自然數N，1≤N≤1000，表示一組方向的長度。
接下來的N行幅行包含下述單詞中的任一個：NORTH(北)、SOUTH(南)、WEST(西)和EAST(東)，表示汽車移動的方向，任何兩個連續的方向都不相同。


輸出描述 Output Description 


輸出文件應包含用R行表示的小鎮的地圖(象輸入文件中一樣)，字符“*”應該僅用來表示汽車最終可能出現的位置。
 


樣例輸入 Sample Input 


4 5
.....
.X...
...*X
X.X..
3
NORTH
WEST
SOUTH
 


樣例輸出 Sample Output 


.....
*X*..
*.*.X
X.X..



這個題也是廣搜題，因為汽車正在行駛時的方向對最終結果有影響，所以BFS的狀態應該是一個三元組(x,y,n)，表示汽車當前坐標位於(x,y)，正在以第n種方向行駛，判重數組也是三維的，BFS過程中狀態轉換時，就沿著第n種方向不斷前進直到有障礙物，其間每經過一個點(newx,newy)，就將狀態(newx,newy,n+1)入隊，BFS循環每次開始時，將隊首出隊，若隊首正在行駛的方向大於n，則說明所有的方向都行駛完了，在地圖上記錄下汽車的最終位置後跳過，記住是跳過！因為汽車的終止位置不止一個 
 
#include 
#include 
#include 

#define MAXN 60
#define MAXM 1100
#define MAXQ 1000000

struct node
{
        int NumOfDir; //當前正在用的方向
        int x,y; //當前車子坐標
}first,q[MAXQ];

int h=0,t=1;
int map[MAXN][MAXN],R,C,sx,sy,n; //map[i][j]=1表示障礙物,2表示車最終可能出現的位置，初始坐標(sx,sy)
int direct[MAXM]; //
int xx[]={-1,1,0,0},yy[]={0,0,-1,1};
bool inQueue[MAXN][MAXN][MAXM]; //判重用數組,inQueue[i][j][n]=true表示車子在(i,j),正在用第n個方向的狀態在隊列裡

bool inMap(int x,int y) //判定(x,y)是否在棋盤內
{
	if(x<1||x>R||y<1||y>C) return false;
	return true;
}

void bfs()
{
        inQueue[first.x][first.y][first.NumOfDir]=true;
        q[h]=first; //初始狀態入隊
        while(hn) //所有的方向都用完了
				{
					map[now.x][now.y]=2;
					continue;
				}
				node next=now;
				next.NumOfDir++;
				while(1)
				{
					next.x+=xx[direct[now.NumOfDir]];
					next.y+=yy[direct[now.NumOfDir]];
					if(map[next.x][next.y]||!inMap(next.x,next.y)) break;
					if(!inQueue[next.x][next.y][next.NumOfDir])
					{
						q[t++]=next;
						inQueue[next.x][next.y][next.NumOfDir]=true;
					}
				}
        }
}

int main()
{
        char s[MAXN];
        scanf("%d%d",&R,&C);
        for(int i=1;i<=R;i++)
        {
                scanf("%s",s+1);
                for(int j=1;j<=C;j++)
                {
                        if(s[j]=='X') map[i][j]=1;
                        else if(s[j]=='*')
                        {
                                sx=i;
                                sy=j;
                        }
                }
        }
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
                scanf("%s",s);
                if(s[0]=='N') direct[i]=0;
                if(s[0]=='S') direct[i]=1;
                if(s[0]=='W') direct[i]=2;
                if(s[0]=='E') direct[i]=3;
        }
        first.x=sx,first.y=sy;
        first.NumOfDir=1;
        bfs();
		for(int i=1;i<=R;i++)
		{
			for(int j=1;j<=C;j++)
			{
				if(map[i][j]==0) printf(".");
				if(map[i][j]==1) printf("X");
				if(map[i][j]==2) printf("*");
			}
			printf("\n");
		}
        return 0;
}