`

HDU 2579 Dating with girls(2)

阅读更多
KIDx 的解题报告
题意很简单:http://acm.hdu.edu.cn/showproblem.php?pid=2579

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

int r, c, mod, step[11][M][M];	//step加维枚举余数所有状态
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};
char map[M][M];
struct pos{
	int x, y, z;
};

void bfs ()
{
	pos ft, tp;
	int i, j, k;
	for (i = 0; i < r; i++)
	{
		for (j = 0; j < c; j++)
		{
			for (k = 0; k < 11; k++)
				step[k][i][j] = inf;    //初始化
			if (map[i][j] == 'Y')		//起点
				ft.x = i, ft.y = j;
		}
	}
	ft.z = 0;
	step[ft.z][ft.x][ft.y] = 0;
	queue<pos> q;
	q.push (ft);
	while (!q.empty())
	{
		ft = q.front();
		q.pop();
		if (map[ft.x][ft.y] == 'G')		//终点
		{
			printf ("%d\n", step[ft.z][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];
			tp.z = (ft.z+1) % mod;
			if (tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c)
				continue;
			if (map[tp.x][tp.y] == '#' && tp.z > 0)		//余数是0才可以走到#
				continue;
			if (step[tp.z][tp.x][tp.y] <= step[ft.z][ft.x][ft.y] + 1)
				continue;	//走过的状态就不用走了
			step[tp.z][tp.x][tp.y] = step[ft.z][ft.x][ft.y] + 1;
			q.push (tp);
		}
	}
	puts ("Please give me another chance!");
}

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

相关推荐

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_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题目java实现

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

    hdu1250高精度加法

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

    ACM HDU题目分类

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

    HDU DP动态规划

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

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

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

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

    HDU-EID-V2-核心板1

    I2C(Inter-Integrated Circuit)接口,如PB6/I2C_SCL(时钟)和PB7/I2C_SDA(数据),用于连接各种外围设备,如传感器和驱动器。 此外,STM32还支持USB(Universal Serial Bus)接口,如PA8/USB_EN(使能)和PA10/...

    hdu2101解决方案

    hdu2101AC代码

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    2. **数据结构**:常用的数据结构包括数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图等,对于不同的问题,选择合适的数据结构能有效提高解题效率。 3. **字符串处理**:杭电ACM中的题目可能涉及到...

    2-sat---hdu3062

    2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    hdu acm1166线段树

    hdu 1166线段树代码

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

    hdu1290解题报告

    ### hdu1290解题报告 #### 题目背景与意义 此题作为对杭州电子科技大学五十周年校庆的献礼,通过一道趣味性的数学问题来庆祝这一重要时刻。题目背景设置在一个充满想象力的情境下,即如何通过不同数量的切刀将一个...

Global site tag (gtag.js) - Google Analytics