(NYoj 284)坦克大战--裸BFS ,优先队列

2024-02-05 02:48

本文主要是介绍(NYoj 284)坦克大战--裸BFS ,优先队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

坦克大战
时间限制:1000 ms | 内存限制:65535 KB
难度:3
描述
Many of us had played the game “Battle city” in our childhood, and some people (like me) even often play it on computer now.
What we are discussing is a simple edition of this game. Given a map that consists of empty spaces, rivers, steel walls and brick walls only. Your task is to get a bonus as soon as possible suppose that no enemies will disturb you (See the following picture).
这里写图片描述
Your tank can’t move through rivers or walls, but it can destroy brick walls by shooting. A brick wall will be turned into empty spaces when you hit it, however, if your shot hit a steel wall, there will be no damage to the wall. In each of your turns, you can choose to move to a neighboring (4 directions, not 8) empty space, or shoot in one of the four directions without a move. The shot will go ahead in that direction, until it go out of the map or hit a wall. If the shot hits a brick wall, the wall will disappear (i.e., in this turn). Well, given the description of a map, the positions of your tank and the target, how many turns will you take at least to arrive there?
输入
The input consists of several test cases. The first line of each test case contains two integers M and N (2 <= M, N <= 300). Each of the following M lines contains N uppercase letters, each of which is one of ‘Y’ (you), ‘T’ (target), ‘S’ (steel wall), ‘B’ (brick wall), ‘R’ (river) and ‘E’ (empty space). Both ‘Y’ and ‘T’ appear only once. A test case of M = N = 0 indicates the end of input, and should not be processed.
输出
For each test case, please output the turns you take at least in a separate line. If you can’t arrive at the target, output “-1” instead.
样例输入
3 4
YBEB
EERE
SSTE
0 0
样例输出
8

分析:
裸的BFS,直接使用优先队列即可。进空格需要一步,进普通砖块需要两步。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;struct node
{int x,y,time;friend bool operator < (node a,node b){return a.time>b.time;}
};
char maze[310][310];
int vis [310][310];
int yx,yy;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int m,n;int bfs()
{memset(vis,0,sizeof(vis));node now,next;now.x=yx;now.y=yy;now.time=0;priority_queue<node> pq;while(!pq.empty()) pq.pop();vis[yx][yy]=1;pq.push(now);while(!pq.empty()){now=pq.top();pq.pop();if(maze[now.x][now.y]=='T'){return now.time;}for(int i=0;i<4;i++){next.x=now.x+dx[i];next.y=now.y+dy[i];if(next.x>=0 && next.x<m && next.y>=0 && next.y<n && !vis[next.x][next.y]){if(maze[next.x][next.y]=='E' || maze[next.x][next.y]=='T'){next.time=now.time+1;vis[next.x][next.y]=1;pq.push(next);}if(maze[next.x][next.y]=='B'){next.time=now.time+2;vis[next.x][next.y]=1;pq.push(next);}}}}return -1;
}int main()
{while(scanf("%d%d",&m,&n)==2 && n && m){for(int i=0;i<m;i++){scanf("%s",maze[i]);for(int j=0;j<n;j++){if(maze[i][j]=='Y'){yx=i;yy=j;}}}printf("%d\n",bfs());}return 0;
}

这篇关于(NYoj 284)坦克大战--裸BFS ,优先队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/679540

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s