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.
3 5 O#### ##### #O#O# 3 4
14
思路:优先队列+bfs(),还有就是我提交了几次。之前那个边界范围弄错了。我是下标从1开始而不是从0开始的。
#include<iostream>
#include<queue>
#include<string.h>
#include<stdio.h>
using namespace std;
char a[500][500];
int c[4]={0,1,0,-1};
int d[4]={1,0,-1,0};
int visited[500][500],b[500][500];
int M,N;
struct point
{
int xx;
int yy;
int cost;
friend bool operator <(point n1,point n2)
{
return n1.cost>n2.cost;
}
};
void bfs(int x,int y)
{
int i;
priority_queue<point>q;
point now,next;
now.xx=1;
now.yy=1;
now.cost=0;
visited[1][1]=1;
q.push(now);
while(!q.empty())
{
next=q.top();
q.pop();
for(i=0;i<4;i++)
{
now.xx=next.xx+c[i];
now.yy=next.yy+d[i];
if(now.xx==x &&now.yy==y)
{
cout<<next.cost+1<<endl;
return ;
}
if(!visited[now.xx][now.yy]&&(now.xx<=M && now.yy<=N &&now.xx>=1 &&now.yy>=1))
{
visited[now.xx][now.yy]=1;
now.cost=next.cost+b[now.xx][now.yy];
q.push(now);
}
}
}
}
int main()
{
int i,j,x,y;
while(cin>>M>>N)
{
memset(visited,0,sizeof(visited));
for(i=1;i<=M;i++) //3 5
{
for(j=1;j<=N;j++)
{
cin>>a[i][j];
if(a[i][j]=='O')
b[i][j]=1;
else if(a[i][j]=='#')
b[i][j]=4;
}
}
cin>>x>>y;
bfs(x,y);
}
return 0;
}