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
//STL容器的用法
//注意不用储存每一个对应的状态,只需要vis标记就可以了,因为这是bfs,会有优先判断
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
int n,m,a,b;
char mp[55][55];
bool vis[55][55];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
struct node
{
int x;
int y;
int step;
bool friend operator<(node a,node b)
{
return a.step>b.step;
}
};
void bfs()
{
priority_queue<node>q;
memset(vis,0,sizeof(vis));
node n1,tmp;
n1.x=0;
n1.y=0;
n1.step=0;
vis[0][0]=1;
q.push(n1);
while(!q.empty())
{
node n2=q.top();
q.pop();
int nx,ny;
for(int k=0; k<4; k++)
{
nx=dx[k]+n2.x;
ny=dy[k]+n2.y;
if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny])
{
if(mp[nx][ny]=='#')
{
tmp.x=nx;
tmp.y=ny;
tmp.step=n2.step+4;
}
else
{
tmp.x=nx;
tmp.y=ny;
tmp.step=n2.step+1;
}
vis[nx][ny]=1;
q.push(tmp);
if(nx== a-1 && ny== b-1)
{
printf("%d\n",tmp.step);
return ;
}
}
}
}
}
int main()
{
while(cin>>n>>m)
{
getchar();
for(int i=0; i<n; i++)
scanf("%s",mp[i]);
cin>>a>>b;
bfs();
}
return 0;
}