POJ1915,这题没啥好说的,rush就完事;
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct
{
int x, y;
int moves;
} point;
queue<point> Qu[2];
bool mp[2][305][305];
int mov[2][305][305];
int dir[8][2] = {
{-2, -1},
{2, -1},
{-2, 1},
{2, 1},
{-1, -2},
{1, -2},
{1, 2},
{-1, 2},
};
int n;
int dbfs(point start, point end)
{
if (start.x == end.x && start.y == end.y)
return 0;
int index = 0;
mp[0][start.x][start.y] = 1;
mp[1][end.x][end.y] = 1;
point head, t, tail;
Qu[0].push(start);
Qu[1].push(end);
while (!Qu[0].empty() || !Qu[1].empty())
{
index ^= 1; //每次都翻转;
int size = Qu[index].size();
for (int j = 0; j < size; j++)
{
head = Qu[index].front();
Qu[index].pop();
//被另一个队列访问过,那么就直接得到结果了;
if (mp[index ^ 1][head.x][head.y])
{
return mov[index][head.x][head.y] + mov[index ^ 1][head.x][head.y];
}
//否则向四周扩散一步;
for (int i = 0; i < 8; i++)
{
int dx = head.x + dir[i][0];
int dy = head.y + dir[i][1];
if (dx >= 0 && dx < n && dy >= 0 && dy < n && !mp[index][dx][dy])
{
t.x = dx;
t.y = dy;
t.moves = head.moves + 1;
mp[index][dx][dy] = true;
mov[index][dx][dy] = head.moves + 1;
Qu[index].push(t);
}
}
}
}
return 0;
}
int main()
{
int t;
point start, end;
cin >> t;
while (t--)
{
//scanf("%d", &n);
cin >> n;
//scanf("%d%d%d%d", &start.x, &start.y, &end.x, &end.y);
cin >> start.x >> start.y >> end.x >> end.y;
memset(mp, 0, sizeof(mp));
memset(mov, 0, sizeof(mov));
while (!Qu[0].empty())
Qu[0].pop();
while (!Qu[1].empty())
Qu[1].pop();
start.moves = 0;
end.moves = 0;
cout << dbfs(start, end) << endl;
}
return 0;
}
原文链接: https://www.cnblogs.com/zhanghanLeo/p/13205806.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/360394
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!