`

HDU 1728 逃离迷宫 + HDU 1072 Nightmare

阅读更多
KIDx 的解题报告
HDU 1728 逃离迷宫 http://acm.hdu.edu.cn/showproblem.php?pid=1728
对于代码31行,为什么等于不能随便剪掉
如果剪掉就会出现下图结果:
【假如转弯数k=1,起点终点如图】
那么如果你的代码是优先向右搜索就会出错
红色的线是先搜的,由于最多转一次弯,所以不合题意;
蓝色是后搜的,因为遇到转弯数相等所以不往下走了了,但是继续走是可以满足题意输出"yes"的


深搜:

#include <iostream>
using namespace std;
#define inf 0x3fffffff
#define M 105
	//1、wan用于转弯数剪枝;2、step用于步数剪枝,就不用vis标记访问了
int r, c, ex, ey, k, wan[M][M];
char map[M][M];
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};
bool flag;

void dfs (int x, int y, int dir)	//dir为当前方向
{
    if (x == ex && y == ey)
    {
        if (wan[x][y] <= k)
            flag = true;
        return ;
    }
	if (wan[x][y] > k)	//转弯数超过k不用往下走了
        return ;
    //x !=ex && y != ey 说明必须至少再转一次弯,但是已经不能再转了
    if (wan[x][y] == k && x !=ex && y != ey)
        return ;
    for (int i = 0; i < 4; i++)
    {
        int tx = x + x_move[i];
        int ty = y + y_move[i];
        if (tx < 0 || tx >= r || ty < 0 || ty >= c)
            continue;
//转弯数相等不可剪掉,所以是wan[tx][ty] < wan[x][y]而不是wan[tx][ty] <= wan[x][y]
        if (map[tx][ty] == '*' || wan[tx][ty] < wan[x][y])	//转弯数剪枝
            continue; 
        if (dir != -1 && i != dir && wan[tx][ty] < wan[x][y] + 1)	//转弯数剪枝
            continue;
        wan[tx][ty] = wan[x][y];
        if (dir != -1 && i != dir)
            wan[tx][ty]++;	//如果方向变了转弯+1
        dfs (tx, ty, i);
        if (flag)
            return ;
    }
}

int main()
{
    int t, i, j, sx, sy;	//sx, sy是起点
    scanf ("%d", &t);
    while (t--)
    {
        scanf ("%d%d", &r, &c);
        for (i = 0; i < r; i++)
            scanf ("%s", map[i]);
        scanf ("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
        sx--, sy--, ex--, ey--;		//我从0开始编号,而题目是从1开始
        for (i = 0; i < r; i++)
            for (j = 0; j < c; j++)
                wan[i][j] = inf;	//初始化转弯数和步数为无穷大
        wan[sx][sy] = 0;	//到达起点的转弯数
        flag = false;
        dfs (sx, sy, -1);	//一开始可以走任意方向,所以设方向为-1
        if (flag)
            puts ("yes");
        else puts ("no");
    }
    return 0;
}

融合深搜思想的广搜【单方向优先扩展】

#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3fffffff
#define M 105

int r, c, sx, sy, ex, ey, wan[M][M], t, k;
char map[M][M];
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};

struct pos{
	int x, y;
};

void bfs ()
{
	int i, j;
	for (i = 0; i < r; i++)
		for (j = 0; j < c; j++)
			wan[i][j] = inf;
	pos ft, tp;
	ft.x = sx, ft.y = sy;
	wan[ft.x][ft.y] = -1;
	queue<pos> q;
	q.push (ft);
	while (!q.empty())
	{
		ft = q.front();
		q.pop();
		if (ft.x == ex && ft.y == ey && wan[ft.x][ft.y] <= k)
		{
			puts ("yes");
			return ;
		}
		for (i = 0; i < 4; i++)
		{
			tp.x = ft.x + x_move[i];
			tp.y = ft.y + y_move[i];
			while (!(tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c))
			{
				if (map[tp.x][tp.y] == '*')
					break;
				if (wan[tp.x][tp.y] < wan[ft.x][ft.y] + 1)
					break;
				wan[tp.x][tp.y] = wan[ft.x][ft.y] + 1;
				if (wan[tp.x][tp.y] > k)
					break;
				if (wan[tp.x][tp.y] == k && tp.x != ex && tp.y != ey)
					break;
				q.push (tp);
				tp.x += x_move[i];
				tp.y += y_move[i];    //单方向优先扩展
			}
		}
	}
	puts ("no");
}

int main()
{
	int t, i;
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%d%d", &r, &c);
		for (i = 0; i < r; i++)
			scanf ("%s", map[i]);
		scanf ("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
		sx--, sy--, ex--, ey--;
		bfs ();
	}
	return 0;
}


HDU 1072 Nightmare http://acm.hdu.edu.cn/showproblem.php?pid=1072
深搜

#include <iostream>
using namespace std;
#define inf 0x3fffffff
#define M 10
	//step[i][j]表示从起点到ij需要的最小步数,T[i][j]表示走到ij诈弹还剩下的时间
int r, c, mins;
int map[M][M], step[M][M], T[M][M];
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};

void dfs (int x, int y)
{
    if (T[x][y] <= 0)	//炸死了
        return ;
    if (map[x][y] == 3)
    {
        if (step[x][y] < mins)
            mins = step[x][y];
        return ;
    }
    for (int i = 0; i < 4; i++)
    {
        int tx = x + x_move[i];
        int ty = y + y_move[i];
        if (tx < 0 || tx >= r || ty < 0 || ty >= c)
            continue;
        if (map[tx][ty] == 0 ||
        step[tx][ty] <= step[x][y] + 1 && T[tx][ty] >= T[x][y] - 1)
            continue;    //已访问过,而且如果走下去诈弹时间没变甚至变小,那还不如不走呢
        step[tx][ty] = step[x][y] + 1;
        T[tx][ty] = T[x][y] - 1;
        if (map[tx][ty] == 4 && T[tx][ty] > 0)
            T[tx][ty] = 6;
        //将诈弹时间置为6,按照题意走到txty必须诈弹还有剩余时间,否则还是要爆
        dfs (tx, ty);
    }
}

int main()
{
    int t, i, j, sx, sy;
    scanf ("%d", &t);
    while (t--)
    {
        scanf ("%d %d", &r, &c);
        for (i = 0; i < r; i++)
        {
            for (j = 0; j < c; j++)
            {
                scanf ("%d", map[i]+j);
                if (map[i][j] == 2)
                    sx = i, sy = j;
                step[i][j] = inf;	//初始化步数为无穷大
            }
        }
        step[sx][sy] = 0;			//到起点的最小步数是0
        memset (T, 0, sizeof(T));	//初始化诈弹剩余时间为0
        T[sx][sy] = 6;				//起点的诈弹初始时间为6
        mins = inf;
        dfs (sx, sy);
        if (mins == inf)
            puts ("-1");
        else printf ("%d\n", mins);
    }
    return 0;
}

广搜
#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3fffffff
#define M 10

int sx, sy, step[M][M], T[M][M], r, c;
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};
int map[M][M];

struct pos{
    int x, y;
};

void bfs ()
{
    int i, j;
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
            step[i][j] = inf, T[i][j] = 0;
    pos ft, tp;
    ft.x = sx, ft.y = sy;
    step[ft.x][ft.y] = 0;
    T[ft.x][ft.y] = 6;
    queue <pos> q;
    q.push (ft);
    while (!q.empty())
    {
        ft = q.front();
        q.pop();
        if (map[ft.x][ft.y] == 3 && T[ft.x][ft.y] > 0)
        {
            printf ("%d\n", step[ft.x][ft.y]);
            return ;
        }
        for (i = 0; i < 4; i++)
        {
            tp.x = ft.x + x_move[i];
            tp.y = ft.y + y_move[i];
            if (tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c)
                continue;
            if (map[tp.x][tp.y] == 0)
                continue;
            if (step[tp.x][tp.y] <= step[ft.x][ft.y] + 1 && 
            T[tp.x][tp.y] >= T[ft.x][ft.y] - 1)
                continue;
            step[tp.x][tp.y] = step[ft.x][ft.y] + 1;
            T[tp.x][tp.y] = T[ft.x][ft.y] - 1;
            if (T[tp.x][tp.y] <= 0)
                continue;
            if (map[tp.x][tp.y] == 4)
                T[tp.x][tp.y] = 6;
            q.push (tp);
        }
    }
    puts ("-1");
}

int main()
{
    int t, i, j;
    scanf ("%d", &t);
    while (t--)
    {
        scanf ("%d%d", &r, &c);
        for (i = 0; i < r; i++)
        {
            for (j = 0; j < c; j++)
            {
                scanf ("%d", map[i]+j);
                if (map[i][j] == 2)
                    sx = i, sy = j;
            }
        }
        bfs ();
    }
    return 0;
}
  • 大小: 10.3 KB
  • 大小: 6.2 KB
  • 大小: 5.9 KB
2
1
分享到:
评论

相关推荐

    HDU+2000-2099+解题报告

    HDU(杭州电子科技大学)在线评测系统是许多编程竞赛爱好者和学习者经常访问的平台,它提供了大量的算法题目供用户练习和挑战。这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、...

    ACM hdu 线段树题目+源代码

    ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    hdu 3341(ac自动机+状态压缩)

    hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

    hdu 1753 大明A+B

    现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...

    hdu 300+ AC 代码

    HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    acm入门之枚举搜索

    acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    "hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDUc++上机测试真题(错题汇集1

    在C++编程语言中,`new`和`delete`是两个关键的操作符,它们与C语言中的`malloc`和`free`有所不同。`new`不仅分配内存,还会根据指定的类型调用对应的构造函数来初始化对象,而`malloc`仅仅分配内存,不涉及对象的...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU图论题目分类

    * 题目1072:Nightmare,涉及到完全搜索的概念。 4. 图的匹配:图的匹配算法、图的稳定匹配等。 * 题目1104:Remainder,涉及到图的匹配算法。 * 题目1105:The Wolves and the Sheep,涉及到图的稳定匹配概念。 5...

    HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.

    【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...

    HDU1059的代码

    HDU1059的代码

Global site tag (gtag.js) - Google Analytics