POJ-3009 Curling2.0

POJ-3009 Curling2.0

Q:On Planet MM-21, after their Olympic games this year, curling is getting popular. But the rules are somewhat different from ours. The game is played on an ice game board on which a square mesh is marked. They use only a single stone. The purpose of the game is to lead the stone from the start to the goal with the minimum number of moves.

解法参照

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#define  MAX_NUM 21
using namespace std;

int H, W;
int dire[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };   //定义四个方向
int minNum = INT_MAX;

void DFS(int map[][MAX_NUM], int x, int y, int step) {     //深搜
    if (step >= 10)                                        //超过10次直接退出
    {
        return;
    }
    for (int i = 0; i < 4; i++)                            //四个方向进行深搜
    {
        int k = x + dire[i][0]; 
        int v = y + dire[i][1];
        if (map[k][v] == 1)                                //如果该方向第一个就是障碍物,下个方向
        {
            continue;
        }
        while (!map[k][v])                                 //找到停止的位置
        {
            k += dire[i][0];
            v += dire[i][1];
        }
        if (k >= 0 && k < H && v >=0 && v < W)             //判断是否越界
        {
            if (map[k][v] == 1)                            //如果是障碍物,则破碎,继续深搜
            {
                map[k][v] = 0;
                DFS(map, k - dire[i][0], v - dire[i][1], step + 1);
                map[k][v] = 1;                             //回溯要复原原来的场景
            }

            if (map[k][v] == 3)
            {
                minNum = step + 1 < minNum ? step + 1 : minNum;
            }
        }
        
    }
}

int main()
{
    int sx, sy, map[MAX_NUM][MAX_NUM];
    while (cin >> W >> H&& W && H)
    {
        for (int i = 0; i < H; i ++)
        {
            for (int j = 0; j < W; j++)
            {
                cin >> map[i][j];
                if (map[i][j] == 2)
                {
                    map[i][j] = 0;
                    sx = i;
                    sy = j;
                }
            }
        }
        minNum = INT_MAX;
        DFS(map, sx, sy, 0);
        if (minNum < INT_MAX)
        {
            cout << minNum << endl;
        }
        else
        {
            cout << -1 << endl;
        }
    }
    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,934评论 0 23
  • 自18世纪起,以纺织业为首的工业革命迅速发展,西方国家的女性悉数成为工厂里纺织女工,随着需求量的阶梯式增长,纺织女...
    小歇哎阅读 225评论 0 1
  • 春回大地,万物复苏。泥土的气息无时无刻不提醒着春天的苏醒,阳光似透着一股浪漫的气息,对,这便是少女的春日。 一日之...
    专属9877阅读 198评论 0 0
  • 六月的天气,有些燥热,有些沉闷,有些阴郁,抬头仰望天空,有不知名的白色鸟儿从天际飞过,划破苍穹,如时光荏苒。 又是...
    奔跑的鸟阅读 249评论 1 1