POJ 3009 Curling 2.0——————dfs

叁歲伎倆 2021-12-01 10:16 172阅读 0赞

# [Curling 2.0][] #

今年的奥运会之后，在行星mm-21上冰壶越来越受欢迎。但是规则和我们的有点不同。这个游戏是在一个冰游戏板上玩的，上面有一个正方形网格。他们只用一块石头。游戏的目的是让石子从起点到终点，并且移动的次数最小

图1显示了一个游戏板的例子。一些正方形格子可能被砖块占据。有两个特殊的格子，起始点和目标点，这是不占用块。（这两个方块是不同的）一旦石头开始移动就不会停下，除非它击中砖块块。为了使石头到达终点，你可以通过让石块击中墙壁或者砖块来停下。

![在这里插入图片描述][aHR0cHM6Ly92ai50aTEyei5jbi9kZmNhZGZmYzIxMTY4NjY1NWMzODJlOWFkOTRiZGJmZQ]  
图1：例子（S：开始，G：目标）

石头的运动遵循以下规则：

开始时，石头静止起点广场上。  
石头的运动仅限于x和y方向。禁止对角线移动。  
当石头静止时，你可以让他向任意方向移动，除非它移动的方向上有砖块（图2（a））。  
一旦抛出，石头不断向同一方向移动，直到下列事件之一发生：

*  石头击中砖块（图2（b），（c））。.  
    石头停在他击中的砖块之前  
    被击中的砖块消失
 *  石块飞出游戏板之外。  
    游戏结束的条件
 *  到达目标点  
    石头停在目标点游戏成功

不能在十步之内到达目标点则返回失败。

![在这里插入图片描述][aHR0cHM6Ly92ai50aTEyei5jbi83MjUxODljZWUxOWI4NmUxY2QyNDEwNDkwYjBkYWRjMg]  
图 2: Stone movements

通过这些规则我们想知道，石头是否能够到达目标点和最少移动次数

初始配置如图1所示，石头从开始到目标需要4次移动。路线如图3所示（a）。注意当石头到达目标时，游戏版的配置如图3（b）改变。

![在这里插入图片描述][aHR0cDovL3Bvai5vcmcvaW1hZ2VzLzMwMDlfMy5naWY]  
图3：图1的解决方案和解决之后的结果。

**Input**  
输入是一组数据。输入结束标志为两个0。数据组的数量不超过100。

每个数据集如下展示

板的宽度（w）和高度（h）  
游戏版的第一行  
…  
游戏版的h-th行

版的宽和高满足: 2 <= w <= 20, 1 <= h <= 20.

每行由一个空格分隔的十进制数字组成。该数字描述相应的格子的状态。

0 空  
1 砖块  
2 开始点  
3 目标点  
图. D-1数据如下:

6 6  
1 0 0 2 1 0  
1 1 0 0 0 0  
0 0 0 0 0 3  
0 0 0 0 0 0  
1 0 0 0 0 1  
0 1 1 1 1 1

**Output**  
对于每个数据，打印一个十进制整数的行，表示从开始到目标的路径的最小移动次数。如果没有这样的路线，打印- 1。每个行不应该有这个数字以外的任何字符。

**Sample Input**  
2 1  
3 2  
6 6  
1 0 0 2 1 0  
1 1 0 0 0 0  
0 0 0 0 0 3  
0 0 0 0 0 0  
1 0 0 0 0 1  
0 1 1 1 1 1  
6 1  
1 1 2 1 1 3  
6 1  
1 0 2 1 1 3  
12 1  
2 0 1 1 1 1 1 1 1 1 1 3  
13 1  
2 0 1 1 1 1 1 1 1 1 1 1 3  
0 0  
**Sample Output**  
1  
4  
\-1  
4  
10  
\-1

--------------------

深搜一下，找准一个方向搜索，直到搜到石头，因为只有碰到石头才能停下然后改变方向

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<bitset>
    #include<set>
    #include<vector>
    
    
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e2+7;
    
    int maze[MAXN][MAXN];
    int dx[] = {
        0, 0, 1, -1};
    int dy[] = {
        1, -1, 0, 0};
    int minStep, n, m;
    
    bool check(int x, int y){
        
            return x>=0 && y>=0 && x<n && y<m;
    }
    
    void dfs(const int& x, const int& y, int step){
        
    
            if(step>10||step>minStep)       return ;
    
            for(int i=0;i<4;++i){
        //方向最重要，我们是根据方向找石头的位置
                    int nx = x;//石头的横坐标
                    int ny = y;//石头的纵坐标
                    while(check(nx, ny)){
        
                            if(maze[nx][ny]==0){
        
                                    nx += dx[i];
                                    ny += dy[i];
                                    continue;//
                            }
                            if(maze[nx][ny]==3){
        
                                    minStep = min(minStep, step+1);
                                    break;
                            }
                            if(maze[nx][ny]==1){
        
    
                                    //不能从挨着的墙走
                                    if(!(nx - dx[i]==x && ny - dy[i]==y)){
        //判断这个位置的墙是不是和起点挨着
                                            maze[nx][ny] = 0;
                                            dfs(nx-dx[i], ny-dy[i], step+1);
                                            maze[nx][ny] = 1;
                                    }
                                    break;
                            }
    
    
                    }
            }
    
    }
    
    int main(){
        
    
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
    
            while(~scanf("%d %d",&m,&n)&&n&&m){
        
                    int sx,sy,x;
                    for(int i=0;i<n;++i)
                            for(int j=0;j<m;++j){
        
                                    cin>>x;
                                    maze[i][j] = x;
                                    if(x==2){
        
                                            sx = i;
                                            sy = j;
    
                                    }
                            }
                    maze[sx][sy] = 0;
                    minStep = 11;
    
                    dfs(sx, sy, 0);
    
                    if(minStep>10)  minStep = -1;
    
                    cout<<minStep<<endl;
    
            }
    
            return 0;
    }

[Curling 2.0]: http://poj.org/problem?id=3009
[aHR0cHM6Ly92ai50aTEyei5jbi9kZmNhZGZmYzIxMTY4NjY1NWMzODJlOWFkOTRiZGJmZQ]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai50aTEyei5jbi9kZmNhZGZmYzIxMTY4NjY1NWMzODJlOWFkOTRiZGJmZQ
[aHR0cHM6Ly92ai50aTEyei5jbi83MjUxODljZWUxOWI4NmUxY2QyNDEwNDkwYjBkYWRjMg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai50aTEyei5jbi83MjUxODljZWUxOWI4NmUxY2QyNDEwNDkwYjBkYWRjMg
[aHR0cDovL3Bvai5vcmcvaW1hZ2VzLzMwMDlfMy5naWY]: /images/20211201/7657ec14dd254bb5884aa35a70b2761d.png