当前位置:首页 > 开发 > 移动开发 > 正文

POJ 2312 Battle City 优先多列+bfs

发表于: 2012-08-14   作者:aijuans   来源:转载   浏览:
摘要: 来源:http://poj.org/problem?id=2312 题意:题目背景就是小时候玩的坦克大战,求从起点到终点最少需要多少步。已知S和R是不能走得,E是空的,可以走,B是砖,只有打掉后才可以通过。 思路:很容易看出来这是一道广搜的题目,但是因为走E和走B所需要的时间不一样,因此不能用普通的队列存点。因为对于走B来说,要先打掉砖才能通过,所以我们可以理解为走B需要两步,而走E是指需要1

来源:http://poj.org/problem?id=2312

题意:题目背景就是小时候玩的坦克大战,求从起点到终点最少需要多少步。已知S和R是不能走得,E是空的,可以走,B是砖,只有打掉后才可以通过。

思路:很容易看出来这是一道广搜的题目,但是因为走E和走B所需要的时间不一样,因此不能用普通的队列存点。因为对于走B来说,要先打掉砖才能通过,所以我们可以理解为走B需要两步,而走E是指需要1步的。因此,不能用普通队列来存。我们可以用STL中的优先队列来存,每次从队头取出的都是步数少的点就可以了。这样最先搜到的就是最优解。

代码:

#include <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
#include <algorithm>
#include <string>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
struct point{
	int x,y,step;
	bool operator < (const point & p) const{
	   return step > p.step;
	} 
};
const int N = 305;
char map[N][N];
int sx,sy,ex,ey,flag[N][N],row,col;
int addx[4] = {0,0,1,-1};
int addy[4] = {1,-1,0,0};
int bfs(){
	priority_queue<point> qq;
	point p;
	p.x = sx; p.y = sy; p.step = 0;
	flag[sx][sy] = 1;
	qq.push(p);
	while(!qq.empty()){
		point topp = qq.top();
		qq.pop();
		if(topp.x == ex && topp.y == ey){
			return topp.step;
		}
		else{
			for(int i = 0; i < 4; ++i){
			   int newx = topp.x + addx[i];
			   int newy = topp.y + addy[i];
			   if(newx >= 0 && newx < row && newy >= 0 && newy < col && !flag[newx][newy] ){
				   if(map[newx][newy] == 'S' || map[newx][newy] == 'R')
					   continue;
			      point newp;
				  newp.x = newx;
				  newp.y = newy;
				  flag[newx][newy] = 1;
				  if(map[newx][newy] == 'B'){
					  newp.step = topp.step + 2;
				  }
				  else
					  newp.step = topp.step + 1;
				  qq.push(newp);
			   }
			}
		}
	}
	return -1;
}
int main(){
	//freopen("1.txt","r",stdin);
	while(scanf("%d%d",&row,&col) != EOF){
	   if(row + col == 0)
		   break;
	   CLR(flag,0);
	   CLR(map,'0');
	   for(int i = 0; i < row; ++i){
	      for(int j = 0; j < col; ++j){
			  cin >> map[i][j];
			  if(map[i][j] == 'Y'){
			    sx = i;
				sy = j;
			  }
			  else if(map[i][j] == 'T'){
			    ex = i;
				ey = j;
			  }
		  }
	   }
	  int ans = bfs();
	  printf("%d\n",ans);
	}
	return 0;
}


POJ 2312 Battle City 优先多列+bfs

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
链接:http://poj.org/problem?id=2312 Battle City Time Limit: 1000MS Memory Limit: 65536K Tota
Battle City Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6880 Accepted: 2326 De
  今天改网盘密码时,找到了个很久前的东西:JavaScript版的坦克大战。07年的夏天制作花了好多个
4、教你通透彻底理解:BFS和DFS优先搜索算法 作者:July 二零一一年一月一日 ---------------------
广度优先遍历是连通图的一种遍历策略。其基本思想如下: 1、从图中某个顶点V0出发,并访问此顶点;
把以前写过的图的广度优先搜索分享给大家(C语言版) 1 #include<stdio.h> 2 #include<std
广度优先搜索(BFS)算法 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一
The Game Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8640 Accepted: 2632 Descr
10047-The Monocycle 3148 35.90% 1014 77.12% <
广度/宽度优先搜索(BFS) 【算法入门】 郭志伟@SYSU:raphealguo(at)qq.com 2012/04/27 1.前言 广度
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号