Algorithm: BFS bằng cách sử dụng queue với map
#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> II;
map<II,int> d;
queue<II> Q;
int x0,y0,x1,y1,N;
int dx8[] = {-1,-1,-1,0,1,1,1,0};
int dy8[] = {-1,0,1,1,1,0,-1,-1};
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin >> x0 >> y0 >> x1 >> y1 >> N;
int r,a,b;
for(int i=0;i<N;i++)
{
scanf("%d %d %d",&r,&a,&b);
for(int i=a;i<=b;i++)
d[II(r,i)] = -1;
}
d[II(x0,y0)] = 0;
Q.push(II(x0,y0));
while(!Q.empty())
{
II top = Q.front();
Q.pop();
for(int i=0;i<8;i++)
{
II cur = II(top.X + dx8[i], top.Y + dy8[i]);
if(d.count(cur) && d[cur] == -1)
{
d[cur] = d[top] + 1;
Q.push(cur);
}
}
}
printf("%d\n",d[II(x1,y1)]);
return 0;
}
Không có nhận xét nào:
Đăng nhận xét