记录编号 |
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;
}