搜索7--noi1804:小游戏

一、心得

二、题目

1804:小游戏

总时间限制:

1000ms

内存限制:

65536kB

描述

一天早上，你起床的时候想：“我编程序这么牛，为什么不能靠这个赚点小钱呢？”因此你决定编写一个小游戏。

游戏在一个分割成w * h个正方格子的矩形板上进行。如图所示，每个正方格子上可以有一张游戏卡片，当然也可以没有。

当下面的情况满足时，我们认为两个游戏卡片之间有一条路径相连：

路径只包含水平或者竖直的直线段。路径不能穿过别的游戏卡片。但是允许路径临时的离开矩形板。下面是一个例子：

这里在 (1, 3)和 (4, 4)处的游戏卡片是可以相连的。而在 (2, 3) 和 (3, 4) 处的游戏卡是不相连的，因为连接他们的每条路径都必须要穿过别的游戏卡片。

你现在要在小游戏里面判断是否存在一条满足题意的路径能连接给定的两个游戏卡片。

输入

输入包括多组数据。一个矩形板对应一组数据。每组数据包括的第一行包括两个整数w和h (1 <= w, h <= 75)，分别表示矩形板的宽度和长度。下面的h行，每行包括w个字符，表示矩形板上的游戏卡片分布情况。使用‘X’表示这个地方有一个游戏卡片；使用空格表示这个地方没有游戏卡片。

之后的若干行上每行上包括4个整数x1, y1, x2, y2 (1 <= x1, x2 <= w, 1 <= y1, y2 <= h)。给出两个卡片在矩形板上的位置（注意：矩形板左上角的坐标是(1, 1)）。输入保证这两个游戏卡片所处的位置是不相同的。如果一行上有4个0，表示这组测试数据的结束。

如果一行上给出w = h = 0，那么表示所有的输入结束了。

输出

对每一个矩形板，输出一行“Board #n:”，这里n是输入数据的编号。然后对每一组需要测试的游戏卡片输出一行。这一行的开头是“Pair m: ”，这里m是测试卡片的编号（对每个矩形板，编号都从1开始）。接下来，如果可以相连，找到连接这两个卡片的所有路径中包括线段数最少的路径，输出“k segments.”，这里k是找到的最优路径中包括的线段的数目；如果不能相连，输出“impossible.”。

每组数据之后输出一个空行。

样例输入

5 4XXXXXX   XXXX X XXX 2 3 5 31 3 4 42 3 3 40 0 0 00 0

样例输出

Board #1:Pair 1: 4 segments.Pair 2: 3 segments.Pair 3: impossible.

来源

翻译自Mid-Central European Regional Contest 1999的试题

三、分析

分析：

1、典型的搜索问题

2、求转弯次数+1

3、可以在方框外面走，我们我们在矩阵的基础上面包一层

4、测试数据的时候列在前面

四、代码

5分

今天先到这，后面再来管

1 //1804:小游戏  2 /*  3 分析：  4 1、典型的搜索问题  5 2、求转弯次数+1  6 3、可以在方框外面走，我们我们在矩阵的基础上面包一层   7 4、测试数据的时候列在前面   8 */  9  10  11  12 #include 
     
       13 using namespace std; 14 //下右上左 分别对应0,1,2,3  15 int goHeight[4]={
   1,0,-1,0}; 16 int goWidth[4]={
   0,1,0,-1}; 17  18   19 char maze[80][80]; 20 int startW,startH,endW,endH; 21 bool vis[80][80]; 22 int w,h; 23 int step;//要求的结果，有几个线段  24 int minStep=0xfffffff;  25 int Board;//案例数  26 int Pair;//每个案例测试数  27  28 void printMaze(){ 29     cout<
      
       <<" "<
       
        <
        
         =minStep) return;  73         for(int i=0;i<4;i++){ 74             int w1=startW+goWidth[i]; 75             int h1=startH+goHeight[i]; 76             if(!vis[h1][w1]&&w1>=0&&w1<=w+1&&h1>=0&&h1<=h+1){ 77                 vis[h1][w1]=true; 78                 int stepBefore=step,directionBefore=direction; 79                 if(direction!=i){ 80                     step++; 81                     direction=i; 82                      83                 } 84                 search(w1,h1,direction,step); 85                 //回溯  86                 vis[h1][w1]=false; 87                 step=stepBefore; 88                 direction=directionBefore; 89             } 90         } 91     }  92 }  93   94 int main(){ 95     //freopen("in.txt","r",stdin); 96     Board=0; 97     while(true){ 98         /* 99         第一步：初始化100         */ 101         //----------------------------------------------------------- 102         103         104         cin>>w>>h;105         if(w==0&&h==0) break;106         cout<<"Board #"<<++Board<<":"<
         
          >startW>>startH>>endW>>endH;141             if(startW==0&&startH==0&&endW==0&&endH==0) break;142             //cout<
          
           <<" "<
           
            <<" "<
            
             <<" "<
             
              <
              
               >m>>n;后161 如果用getchar()读取，读到的是行尾的"/n"; 162 2、163 目的点是有卡片的，默认情况不能走，我们要让它可走 164 vis[endH][endW]=false;165 3、166 这里是所有解中的最优解，所以是回溯而非DFS167 那就要记录所有解，找到最优解 168 4、169 优化一：如果中间的step大于了minStep，说明肯定不是最优解170 if(step>=minStep) return; 171 5、172 上一个目的地变成可走后，到下一个测试的要变成卡片 173 6、174 在每个起点终点测试的前面，要给minStep赋初值 175 */