递归小游戏

Posted on | In |

问题描述
• 当下面的情况满足时,
认为两个游戏卡片之间有一条路径相连:
• 路径只包含水平或者竖直的直线段
• 路径不能穿过别的游戏卡片
• 但是允许路径临时的离开矩形板

输入 (1/2)
• 输入包括多组数据: 一个矩形板对应一组数据
• 第一行包括两个整数 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.”
• 每组数据之后输出一个空行
7
样例输入
5 4
X X X X X

X X

X X X X

X X X

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.
用bfs实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<string.h>
#include<queue>
struct Point{
    int x;
    int y;
    int f;
    Point(int xx,int yy,int ff):x(xx),y(yy),f(ff){
    }
};
using namespace std;
int board[100][100];
char maze[100][100];
int mark[100][100];
int dis[100][100];
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int w,h;
int inBoard(int n,int x0,int y0){
    return n>=x0&&n<y0;
}
bool bfs(int x0,int y0,int x1,int y1,int cnt){
    memset(mark,0,sizeof(mark));
    memset(dis,0,sizeof(dis));
    queue<Point> q;
    Point P=Point(x0,y0,-1);
    q.push(P);
    mark[x0][y0]=1;
    dis[x0][y0]=0;
    while(!q.empty()){
        Point u=q.front();
        q.pop();
        int now_x=u.x;
        int now_y=u.y;
        for(int i=0;i<4;i++){
            int x=now_x+d[i][0];
            int y=now_y+d[i][1];
            if(x==x1&&y==y1){
                dis[x][y]=dis[now_x][now_y]+1;
                cout<<"Pair "<<cnt<<":"<<dis[x][y]<<" segments."<<endl;
                return true;
            } 
            if(inBoard(x,0,h+2)&&inBoard(y,0,w+2)&&!mark[x][y]&&board[x][y]==0){
                q.push(Point(x,y,i));
                if(u.f!=i)
                {
                    dis[x][y]=dis[now_x][now_y]+1;//!!!
                }
                else dis[x][y]=dis[now_x][now_y];
                mark[x][y]=1;
            }
            
        }
    }
    return false;
    
}
int main(){
    int x0,y0,x1,y1;
    memset(board,0,sizeof(board));
    int cnt=1;
    while(scanf("%d%d",&w,&h)){
    
        if(w==0&&h==0) break;
        for(int i=1;i<=h;i++){
            getchar();//!!!
            for(int j=1;j<=w;j++){
            maze[i][j] = getchar();
            }   
        }

        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++){
                if(maze[i][j]=='X') board[i][j]=1;
            }   
        }       

        int Count=1;
            cout<<"Board #"<<cnt<<endl;
        while(scanf("%d%d%d%d",&y0,&x0,&y1,&x1))
    {
        
        if(x0==0&&y0==0&&x1==0&&y1==0) break;
        
    if(!    bfs(x0,y0,x1,y1,Count)) cout<<"Pair "<<Count<<":""impossible."<<endl;
        Count++;
    }       
    cnt++;  
    }
    
    
    return 0; 
}

image