一、深度优先搜索

二、广度优先搜索

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; map
       
        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
         
         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表示车最终可能出现的位置，初始坐

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1733带权并查集	下一篇：poj-2492- A Bug's Life

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: