记录编号	198452	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Feb07] 青铜莲花池	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-10-25 07:07:20	内存使用	2.23 MiB

#include<cstdio>
#include<queue>
using namespace std;
int x[10],y[10];
int n,m,mi,mo,Ans=999999999;
int xa,ya,xb,yb;
int a[500][500],b[500][500];
bool vis[150][150];
struct dt{
	int x,y,step;
}at,aot;
void Get_Pre(){
	x[1]=mi,y[1]=mo;x[2]=mi; y[2]=-mo;
	x[3]=-mi;y[3]=mo;x[4]=-mi; y[4]=-mo;
	x[5]=mo; y[5]=-mi; x[6]=-mo; y[6]=-mi;
	x[7]=-mo;y[7]=mi; x[8]=mo;y[8]=mi;
}
void bfs(int s,int r,int step){
	queue<dt>que;
	at.x=s; at.y=r;at.step=step;
	que.push(at);
	while(!que.empty()){
		at=que.front();que.pop();
		if(at.x==xb&&at.y==yb) Ans=at.step;
		vis[at.x][at.y]=1;
		for(int i=1;i<=8;++i){
			int as=at.x+x[i];
			int bs=at.y+y[i];
			if(as>0&&as<=n&&bs>=1&&bs<=m&&!b[as][bs]&&!vis[as][bs]){
				aot.x=as; aot.y=bs; aot.step=at.step+1;
				b[as][bs]=1;
				que.push(aot);
			}
	     }
	}
	
}
int main(){
    freopen("bronlily.in","r",stdin);
	freopen("bronlily.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&mi,&mo);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
			if(a[i][j]==0) b[i][j]=1;
			if(a[i][j]==2) b[i][j]=1;
			if(a[i][j]==1) b[i][j]=0;
			if(a[i][j]==3){
				xa=i; ya=j; b[i][j]=0;
			}
			if(a[i][j]==4){
				xb=i;yb=j; b[i][j]=0;
			}
		}
	}
	Get_Pre();
	bfs(xa,ya,0);
	printf("%d",Ans);
	getchar();getchar();
	return 0;
}
/*
12 15 2 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 3 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/