NYOJ - 635 - Oh, my goddess(BFS,優先隊列)

描述

Shining Knight is the embodiment of justice and he has a very sharp sword can even cleavewall. Many bad guys are dead on his sword.

One day, two evil sorcerer cgangee and Jackchess decided to give him some colorto see. So they kidnapped Shining Knight's beloved girl--Miss Ice! They built a M x Nmaze with magic and shut her up in it.

Shining Knight arrives at the maze entrance immediately. He can reach any adjacent emptysquare of four directions -- up, down, left, and right in 1 second. Or cleave one adjacent wall in 3

seconds, namely,turn it into empty square. It's the time to save his goddess! Notice: ShiningKnight won't leave the maze before he find Miss Ice.

輸入

The input consists of blocks of lines. There is a blank line between two blocks.

The first line of each block contains two positive integers M <= 50 and N <= 50separated by one space. In each of the next M lines there is a string of length N contentsO and #.

O represents empty squares. # means a wall.

At last, the location of Miss Ice, ( x, y ). 1 <= x <= M, 1 <= y <= N.

(Shining Knight always starts at coordinate ( 1, 1 ). Both Shining and Ice's locationguarantee not to be a wall.)

輸出

The least amount of time Shining Knight takes to save hisgoddess in one line.

樣例輸入

3 5
O####
#####
#O#O#
3 4      

樣例輸出

14      

思路：看了題目後，題目要求是從A點到B點，求出最短路。由于到某個點所需要走的步數不一樣，走到#需要4步，O需要一步，是以求最短路要用優先隊列。

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

int x1,y1,x2,y2,ans,n,m;
int vis[55][55];
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
char map[55][55];


struct Point{
	int x,y,steps;
	friend bool operator<(Point a,Point b){
		return a.steps>b.steps;
	}
};


void bfs(){
	if(x1==x2&&y1==y2){
		ans = 0;
		return ;
	}
	priority_queue<Point>q;
	Point v1;
	v1.x = x1;
	v1.y = y1;
	v1.steps = 0;
	vis[x1][y1] = 1;
	q.push(v1);	
	
	while(!q.empty()){
		Point v2;
		for(int i=0 ;i<4 ;i++){
			v2.x = q.top().x + dir[i][0];
			v2.y = q.top().y + dir[i][1];

			if(v2.x>=0&&v2.y>=0&&v2.x<n&&v2.y<m&&!vis[v2.x][v2.y]){
				if(v2.x==x2&&v2.y==y2){
					ans = q.top().steps+1;
					break;
				}
				
				if(map[v2.x][v2.y]=='#'){
					v2.steps = q.top().steps+4;
				}else{
					v2.steps = q.top().steps+1;
				}
				vis[v2.x][v2.y] = 1;
				q.push(v2);
			}
		}
		if(v2.x==x2&&v2.y==y2){
			break;
		}
		q.pop();
	}
	
	
	
}

int main(){
	while(scanf("%d%d",&n,&m)!=EOF&&n&&m){
		memset(vis,0,sizeof(vis));
		x1=0; y1=0; ans=-1;
	
		for(int i=0 ;i<n ;i++){
			scanf("%s",map[i]);
		}

		scanf("%d%d",&x2,&y2);
		x2 --;
		y2 --;
		bfs();
		printf("%d\n",ans);
	}
	return 0;
}