nyoj284 坦克大战(dijkstra(dfs+优先队列))

坦克大战

时间限制: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
来源
POJ
上传者
sadsad
做这道题吧我累死了。。。哎。写个博客歇歇0.0
让我看这道题,我认为就是最短路径问题。当然,关键看你能不能往那里去想,想到了其实也是很简单的。也就是dijkstra,看评论区别人都是用dfs+优先队列,不还是dijkstra思想嘛。。
如果还不懂dijkstra思想的同学建议找度娘。。。
其实这道题我错了整整一页,因为我认为我一直是对了。改改格式什么的。还是不行,最后瞟了一眼map[304][30]....果然手残漏打了一个4...
改了就AC了。希望那些如果认为自己代码正确的童鞋多看看细节。而且是那种最不容易想到的简单的地方。
奉上代码
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
struct node
{
	int x,y,step;
	friend	bool operator <(node a,node b)
	{
		return a.step>b.step;
	}
};
priority_queue<node> s;//结构体优先队列
char map[304][304];
int m,n,visit[304][304],dir[4][2]={1,0,-1,0,0,1,0,-1};//vis标记是否访问,dir代表四个方向
bool limit(int x,int y)//判断是否出界和此刻指向的位置是否是水和石头
{
	if(x>=0&&y>=0&&x<m&&y<n&&map[x][y]!='S'&&map[x][y]!='R')
	return true;
	else
	return false;
}
int tonum(char c)//把对应的字母转换为需要的步数
{
	if(c=='B')
	return 2;
	if(c=='E'||c=='T')
	return 1;
}
int dfs(int star,int end)
{
	node temp,sta;
	visit[star][end]=1;//Y位置标记为1
	temp.x=star,temp.y=end,temp.step=0;
	s.push(temp);
	while(!s.empty())//完全是dijkstra思想 看不懂的百度吧
	{
		int ant;
		temp=s.top();
		s.pop();
		star=temp.x,end=temp.y,ant=temp.step;
		for(int i=0;i<4;i++)
		{
			temp.x+=dir[i][0];
			temp.y+=dir[i][1];
			if(limit(temp.x,temp.y)&&!visit[temp.x][temp.y])
			{
				visit[temp.x][temp.y]=1;
				temp.step+=tonum(map[temp.x][temp.y]);
				if(map[temp.x][temp.y]=='T')
				return temp.step;
				s.push(temp);
			}
			temp.x=star,temp.y=end,temp.step=ant;
		}
	}
	return -1;
}
int main()
{
	int star_x,star_y;
	while(scanf("%d %d",&m,&n)!=EOF&&(m||n))
	{
		for(int i=0;i<m;i++)
		scanf("%s",map[i]);
		for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
		{
			if(map[i][j]=='Y')
			star_x=i,star_y=j;
		}
		memset(visit,0,sizeof(visit));
		printf("%d\n",dfs(star_x,star_y));
		while(!s.empty())
		s.pop();
		memset(map,0,sizeof(map));
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 07-12

nyoj284 坦克大战(dijkstra(dfs+优先队列))的相关文章

nyoj-----284坦克大战(带权值的图搜索)

坦克大战 时间限制: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 co

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 co

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 co

DS课设【坦克大战最短路】(MummyDing)

DS课设[坦克大战最短路] 还是决定写点东西简单记录下这次编码. 一.想法 还没放假的时候只想着用C#实现,算法图论方面觉得图论方向会靠谱些,但一直没有什么好点子.C#以前也没学过,自信来源于MFC的学习经历(以前也是用它做了C语言课设).C#应该是没有MFC那么复杂的,心想看几天应该就可以上手一些小东西了,事实证明也如此. 寒假时间相对以前更长,也并不着急做课设.开始一段是刷题+学习Kinect+顺带了解Kinect,后来在刷题过程中遇到这题,还蛮有意思的,当即就写了个"坦克大战最短路简单设计

坦克大战系列(3.0版)

无论头上是怎样的天空,我准备承受任何风暴.--拜伦 本讲内容:坦克3.0版(面向对象的思想) 要求:画出我方坦克会动并且会发射子弹.画出敌人坦克 一.同一个包下建二个文件分别为:MyTankGame.Members(负责其它成员譬如:制造坦克.子弹等) MyTankGame类 /** * 功能:坦克游戏的3.0版本 * 1:画出坦克 * 2:实现我方坦克移动并且會發子彈,并 画出敌人的坦克 */ package a; import javax.swing.*; import java.awt.*

C++代码训练之坦克大战(2)

这一篇中,我们继续继续进行我们的坦克大战. 位置信息数据结构 在游戏设计过程中,需要记录大量的位置信息,如果仅仅使用(x,y)坐标很容易出错.这一篇中,我们先定义两个简单的数据结构用来保存点和矩形的信息. 在项目中新建Model目录,创建下面四个文件: 代码如下: Point.h #ifndef __POINT_H__ #define __POINT_H__ class Point { public: Point(int x = 0, int y = 0) : m_x(x), m_y(y){};

坦克大战(版本2.5-版本2.9)

版本2.5 功能:添加“血块”步骤:        1)添加blood类        2)添加必要的方法:eat方法等        3)让blood对象固定轨迹运动, 并在一定时间后消失 具体代码实现: 新增的blood类: 1 import java.awt.Color; 2 import java.awt.Graphics; 3 import java.awt.Rectangle; 4 5 //模拟血块,坦克吃了可以补血 6 public class Blood { 7 int x, y

脚本游戏之四: 坦克大战源码注释(待续。。。)

要点: 1.echo的高级用法,主要包括:颜色.位置定位输出等 2.trap 信号捕捉, kill 发送信号 3.捕捉用户输入,控制后台进程 参考:坦克大战 文章结尾的几段代码 总体: 多个进程后台并行运行, 前端一个段接受用户输入的代码,根据用户输入通过发送信号控制后台进程. 几乎每一个组件都是一个后台运行的函数. #!/bin/bash # BY: LingYi # DATE: 2016.02.23 #place temporary files tmpdir='/tmp' #u:up d:d

Java__线程---基础知识全面实战---坦克大战系列为例

今天想将自己去年自己编写的坦克大战的代码与大家分享一下,主要面向学习过java但对java运用并不是很熟悉的同学,该编程代码基本上涉及了java基础知识的各个方面,大家可以通过练习该程序对自己的java进行一下实战. 每个程序版本代码中,都附有相关注释,看完注释大家就可以对本程序设计有个很明显的思路.真的很有趣,想对java重新温习的同学完全不必再对厚厚的java基础书籍进行阅读了,在跟着本次代码练习并分析后,大家一定会对java各方面基础知识 尤其是线程的知识有更深一步的了解!!! 本次坦克大