搜索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 4
XXXXX
X   X
XXX X
 XXX 
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0

样例输出

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

来源

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

  1 //1804:小游戏
  2 /*
  3 分析：
  4 1、典型的搜索问题
  5 2、求转弯次数+1
  6 3、可以在方框外面走，我们我们在矩阵的基础上面包一层 
  7 4、测试数据的时候列在前面 
  8 */
  9 
 10 
 11 
 12 #include <iostream>
 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<<w<<" "<<h<<endl;
 30     for(int i=1;i<=h;i++){
 31         for(int j=1;j<=w;j++){
 32             cout<<maze[i][j];
 33         }
 34         cout<<endl;
 35     } 
 36 }
 37 
 38 void printVis(){
 39     cout<<w<<" "<<h<<endl;
 40     for(int i=0;i<=h+1;i++){
 41         for(int j=0;j<=w+1;j++){
 42             cout<<vis[i][j]<<" ";
 43         }
 44         cout<<endl;
 45     } 
 46 }
 47 
 48 void printAns(int minStep){
 49     
 50     if(minStep==0xfffffff){
 51         cout<<"Pair "<<Pair++<<": impossible."<<endl;
 52     }
 53     else{
 54         cout<<"Pair "<<Pair++<<": "<<minStep<<" segments."<<endl;
 55     }
 56 } 
 57 
 58 /*
 59 函数说明，
 60 有当前的朝向 (下右上左 分别对应0,1,2,3 )
 61 有当前的坐标 (保证DFS往下走)
 62 有转弯次数+1 (结果) :是int，如果是0，说明无解，是大于0的数，则说明解释那个数 
 63 */ 
 64 void search(int startW,int startH,int direction,int step){
 65     //cout<<"startW: "<<startW<<" startH:"<<startH<<" direction:"<<direction<<" step:"<<step<<endl;
 66     //printVis(); 
 67     if(startW==endW&&startH==endH){
 68         if(step<minStep) minStep=step;
 69     }
 70     else{
 71         //优化一：如果中间的step大于了minStep，说明肯定不是最优解
 72         if(step>=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<<":"<<endl;
107         //把矩阵的外面至为可访问的
108         for(int i=0;i<=max(w,h);i++){
109             //左上交 
110             vis[0][i]=false;
111             vis[i][0]=false;
112             //右下角：宁可杀错，也不放过 
113             vis[h+1][i]=false;
114             vis[w+1][i]=false;
115             vis[i][h+1]=false;
116             vis[i][w+1]=false;
117         } 
118         //输入maze
119         for(int i=1;i<=h;i++){
120             getchar();
121             for(int j=1;j<=w;j++){
122                 char c=getchar();
123                 maze[i][j]=c;
124                 if(c==‘X‘) vis[i][j]=true; 
125             }
126         } 
127         
128         Pair=1;
129         
130         //print函数
131         //printMaze(); 
132         //printVis();
133         
134         /*
135         第二步：搜索计算
136         */ 
137         //-------------------------------------------------------- 
138         while(true){
139             minStep=0xfffffff; 
140             cin>>startW>>startH>>endW>>endH;
141             if(startW==0&&startH==0&&endW==0&&endH==0) break;
142             //cout<<startW<<" "<<startH<<" "<<endW<<" "<<endH<<endl;
143             //初始化步数 
144             step=0; 
145             //让目的地变的可走 
146             vis[endH][endW]=false;
147             search(startW,startH,4,step);//默认的朝向是自由的,这是从起点开始计算线段 
148             printAns(minStep);
149             //上一个目的地变成可走后，到下一个测试的要变成卡片 
150             vis[endH][endW]=true;
151         } 
152     }
153     
154     
155     return 0;
156 } 
157 /*
158 1、 
159 输入为：5 4
160 cin>>m>>n;后
161 如果用getchar()读取，读到的是行尾的"/n"; 
162 2、
163 目的点是有卡片的，默认情况不能走，我们要让它可走 
164 vis[endH][endW]=false;
165 3、
166 这里是所有解中的最优解，所以是回溯而非DFS
167 那就要记录所有解，找到最优解 
168 4、
169 优化一：如果中间的step大于了minStep，说明肯定不是最优解
170 if(step>=minStep) return; 
171 5、
172 上一个目的地变成可走后，到下一个测试的要变成卡片 
173 6、
174 在每个起点终点测试的前面，要给minStep赋初值 
175 */