炸弹时间复位

题目大意:

该题为走迷宫,其条件有如下6个:

1, 迷宫用二维数组来表示;

2, 人走动时不能越界,不能在墙上走;

3, 当走到出口时,若剩余时间恰好为0,则失败;

4, 找到炸弹复位装置,若剩余时间恰好为0,则不能使用;

5, 炸弹复位装置可以使用若干次;

6, 只要走到复位装置所在位置,时间自动复置为6;

其中,数组中,0表示墙,1表示通道,2表示初始位置,3表示出口,4表示炸弹复位装置;

求走出迷宫所需要的最少步数,若不能在炸弹爆炸前走出来,输出-1.

大概思路:

迷宫问题是经典的BFS问题,首先获取初始位置,调用队列,使其入队,定义方向数组,分别用(0,-1)、(-1,0)、(0,1)、(1,0)表示下上左右四个方向,对当前位置的四个方向进行判定,若能走得通,则使其入队。

没啥说的,非常经典的广度优先搜索

至于为啥坐了一晚上没对,原因太尴尬

努力改正这样的毛病吧

这个东西,不细心真的不行

#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
int x;
int y;
int step;
int time;
};
queue<node>Q;
int f[4][2]={0,-1,0,1,-1,0,1,0};
int a[505][505];
int m,n;
int bfs(int x,int y)
{
node q={x,y,0,6};
a[q.x][q.y]=0;
Q.push(q);
while(!Q.empty())
{
node e,w;
e=Q.front();
Q.pop();
for(int i=0;i<4;i++)
{
w.x=e.x+f[i][0];
w.y=e.y+f[i][1];
w.time=e.time-1;
w.step=e.step+1;
if(w.x>=0&&w.y>=0&&w.x<m&&w.y<n&&a[w.x][w.y]!=0&&w.time>0)
{
if(a[w.x][w.y]==3)
{
return w.step;
}
if(a[w.x][w.y]==4)
{
w.time=6;
}
Q.push(w);
a[w.x][w.y]=0;
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{

scanf("%d%d",&m,&n);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(a[i][j]==2)
printf("%d\n",bfs(i,j));
}
}
while(!Q.empty())
Q.pop();
memset(a,0,sizeof(a));

/*这个while和这个memset有必要说一下

每次处理完一组数据之后都要把使用的东西初始化

包括队列清空,数组归零,申请的空间要释放等等

要养成良好的习惯*/
}
return 0;
}

时间: 03-03

炸弹时间复位的相关文章

Nightmare --- 炸弹时间复位

题目大意: 该题为走迷宫,其条件有如下6个: 1, 迷宫用二维数组来表示: 2, 人走动时不能越界,不能在墙上走: 3, 当走到出口时,若剩余时间恰好为0,则失败: 4, 找到炸弹复位装置,若剩余时间恰好为0,则不能使用: 5, 炸弹复位装置可以使用若干次: 6, 只要走到复位装置所在位置,时间自动复置为6: 其中,数组中,0表示墙,1表示通道,2表示初始位置,3表示出口,4表示炸弹复位装置: 求走出迷宫所需要的最少步数,若不能在炸弹爆炸前走出来,输出-1. 大概思路: 迷宫问题是经典的BFS问

hdu 1072(BFS) 有炸弹

http://acm.hdu.edu.cn/showproblem.php?pid=1072 题目大意是在一个n×m的地图上,0表示墙,1表示空地,2表示人,3表示目的地,4表示有定时炸弹重启器. 定时炸弹的时间是6,人走一步所需要的时间是1.每次可以上.下.左.右移动一格. 当人走到4时如果炸弹的时间不是0,可以重新设定炸弹的时间为6.如果人走到3而炸弹的时间不为0时, 成功走出.求人从2走到3的最短时间. 一道典型的搜索,用的bfs,结构体中开一个step表示要求的时间,也就相当于步数,一个

HDU 1072 Nightmare( 身上带有定时炸弹的他能否在炸弹爆炸之前离开—— BFS+DP思想)

Nightmare Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Description Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the

技能的释放与CD

1 using UnityEngine; 2 using System.Collections; 3 using UnityEngine.UI; 4 5 public class skill : MonoBehaviour 6 { 7 8 public static skill _instance;//设为静态变量 9 private Image fillColding; 10 public float coldTimer = 1; 11 private float time = 0; 12 p

HDU_1072_Nightmare

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1072 题目描述:矩阵表示迷宫,0表示墙,1表示路,2表示起点,3表示终点,4表示重置炸弹时间(6秒),你需要从起点出发(炸弹初始为6秒),在炸弹爆炸前到达终点,问最少需要多少时间. 分析:dfs,可以走走过的路,所以不能使用vis数组来标记,而是用dis和tim两个数组来帮助判断所走路线,通过这两个数组的记录来剪枝(此处剪枝:当sum大于dis[x][y]且time<=tim[x][y]说明当前这条路并

嵌入式Linux裸机开发(九)——S5PV210定时器

嵌入式Linux裸机开发(九)--S5PV210定时器 S5PV210内部一共有四类定时器. 一.PWM定时器 1.PWM定时简介 S5PV210内部共有5个32bit的PWM定时器.PWM定时器可以生成内部中断.PWM定时器0.1.2.3具有PWM功能,可以驱动外部I/O信号.PWM定时器4是一个无外部引脚的内部定时器.PWM 定时器使用 PCLK_PSYS 作为时钟源. 每个定时器有一个由定时器时钟驱动的32位递减计数器.递减计数器的初始值是由TCNTBn自动装载而获得的.如果递减计数器减到

MiS603开发板 2.4 Testbench设计

作者:MiS603开发团队 日期:20150911 公司:南京米联电子科技有限公司 论坛:www.osrc.cn 网址:www.milinker.com 网店:http://osrc.taobao.com EAT博客:http://blog.chinaaet.com/whilebreak 博客园:http://www.cnblogs.com/milinker/ 2.4 Testbench设计 一个完整的设计,除了好的功能描述代码,对于程序的仿真验证是必不可少的.学会如何去验证自己所写的程序,即如

HDU1072 Nightmare 【BFS】

Nightmare Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7367    Accepted Submission(s): 3530 Problem Description Ignatius had a nightmare last night. He found himself in a labyrinth with a ti

hdoj 1072 Nightmare 【bfs】

Nightmare Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8568    Accepted Submission(s): 4107 Problem Description Ignatius had a nightmare last night. He found himself in a labyrinth with a ti