记录编号	150161	评测结果	AA
题目名称	最少转弯问题	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2015-02-28 07:41:17	内存使用	0.36 MiB

#include <iostream>
#include <queue>
#include <fstream>

using namespace std;

ifstream fin ("turn.in");
ofstream fout ("turn.out");
int n, m, x1, x2, y1, y2, s, pd[110][110],
	der[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
struct DATA {
	int x, y, tur, dir;
};
queue<DATA> q;

void init(), bfs();


int main()
{
	init();
	
	bfs();
	
	fout << s;
	fin.close ();
	fout.close ();
	return 0;
}


void init()
{
	DATA lp;
	fin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++)
		{
			fin >> pd[i][j];
			if (pd[i][j] == 1) {
				pd[i][j] = -1;
			}
			else {
				pd[i][j] = 0xffffff;
			}
		}
	}
	fin >> x1 >> y1 >> x2 >> y2;
	lp.x = x1, lp.y = y1, lp.tur = 0, lp.dir = 4;
	q.push (lp);
	return;
}

void bfs()
{
	int nx, ny, ntur;
    while (! q.empty())
	{
		for (int i = 0; i < 4; i ++)
		{
			nx = q.front ().x + der[i][0];
			ny = q.front ().y + der[i][1];
			if (q.front ().dir == i) {
				ntur = q.front ().tur;
			}
			else {
				ntur = q.front ().tur + 1;
			}
			if (nx>0&&ny>0&&nx<=n&&ny<=m&&pd[nx][ny]>=0&&ntur<pd[nx][ny])
			{
				DATA lp;
				pd[nx][ny] = ntur;
				lp.x = nx;
				lp.y = ny;
				lp.dir = i;
				lp.tur = ntur;
				q.push (lp);
			}
			if (q.back ().x == x2 && q.back ().y == y2)
			{
				s = q.back ().tur - 1;
				return;
			}
		}
		q.pop ();
    }
    return;
}