记录编号	165773	评测结果	AA
题目名称	最少转弯问题	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2015-06-12 21:05:56	内存使用	0.32 MiB

#include <cstring>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

pair <int,int> cow1,cow2;

class three{
	public:
		pair <int,int> d;
		int step;
};

int n,m;
int gx[4]={0,0,1,-1};
int gy[4]={1,-1,0,0};
bool map[101][101];
bool v[101][101];

void bfs(){
	int i,j;
	queue <three> q;
	q.push((three){
		cow1,-1
	});
	v[cow1.first][cow1.second]=1;
	int steps=-1;
	three temp;
	while(!v[cow2.first][cow2.second]){
		steps++;
		while(q.front().step<steps){
			temp=q.front();
			q.pop();
			for(i=0;i<4;i++){
				int qx=temp.d.first+gx[i];
				int qy=temp.d.second+gy[i];
				for(;qx>=1&&qy>=1&&qx<=n&&qy<=m&&!map[qx][qy];qx+=gx[i],qy+=gy[i]){
					if(v[qx][qy])
					    continue;
					v[qx][qy]=1;
					q.push((three){
						make_pair(qx,qy),steps
					});  
				}
			}
		}
	}
	printf("%d",steps);
}

int main(){
	freopen("turn.in","r",stdin);
	freopen("turn.out","w",stdout);
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",&map[i][j]);
	int ax,ay,bx,by;//x1 y1 x2 y2
	scanf("%d%d%d%d",&ax,&ay,&bx,&by);
	cow1=make_pair(ax,ay);
	cow2=make_pair(bx,by);
	bfs();		
}