记录编号	300957	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Feb07] 青铜莲花池	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2016-08-29 16:19:27	内存使用	0.30 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int map[35][35];
bool vis[35][35];
int dx[10],dy[10];
int m,n,m1,m2;
int bx,by,ex,ey;
char c;
struct Node{
	int x,y,step;
	Node(int a=0,int b=0,int z=0){ x=a,y=b,step=z;	}		
};
queue<Node> q;
int main()
{
	freopen("bronlily.in","r",stdin);
	freopen("bronlily.out","w",stdout);
    scanf("%d%d%d%d",&m,&n,&m1,&m2);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++){
            cin>>c;
        	if(c=='4')ex=i,ey=j,map[i][j]=1;    
            if(c=='3')bx=i,by=j,map[i][j]=1;
            if(c=='1')map[i][j]=1;
        }
    }
    dx[1]=m1,dx[2]=m1,dx[3]=m2,dx[4]=m2,dx[5]=-m1,dx[6]=-m1,dx[7]=-m2,dx[8]=-m2;
    dy[1]=-m2,dy[2]=m2,dy[3]=-m1,dy[4]=m1,dy[5]=m2,dy[6]=-m2,dy[7]=m1,dy[8]=-m1;
    q.push(Node(bx,by,0));
    Node a,b;
    while(!q.empty())
    {
		a=q.front();
		q.pop();
		for(int i=1;i<=8;i++)
		{
			b=a;
			b.x=a.x+dx[i];
			b.y=a.y+dy[i];
			b.step=a.step+1;
			if(b.x>m||b.y<1||b.y>n||b.x<1)continue;
			if(b.x==ex&&b.y==ey)
			{
				printf("%d\n",b.step);
				return 0;
			}
			if(map[b.x][b.y]==1&&!vis[b.x][b.y])
			{
				vis[b.x][b.y]=1;
				q.push(b);
			}
		}
	}
	return 0;
}