Pagini recente » Cod sursa (job #2151812) | Cod sursa (job #2653979) | Cod sursa (job #2269962) | Cod sursa (job #1807757) | Cod sursa (job #865847)
Cod sursa(job #865847)
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair
using namespace std;
ifstream cin("car.in");
ofstream cout("car.out");
const int dx[] = {-1,-1,0,1,1,1,0,-1}, dy[] = {0,1,1,1,0,-1,-1,-1};
const int NMAX = 512, inf = int(1e9);
int N, M;
bool isFree[NMAX][NMAX];
int cost[NMAX][NMAX];
int reached[NMAX][NMAX];
pii S, D;
void readData() {
cin>>N>>M;
cin>>S.x>>S.y>>D.x>>D.y;
for(int i = 1;i <= N;i++) {
for(int j = 1;j <= M;j++) {
cin>>isFree[i][j];
}
}
}
int bf() {
for(int i = 1;i <= N;i++) {
for(int j = 1;j <= M;j++) {
cost[i][j] = inf;
isFree[i][j] = !isFree[i][j];
}
}
queue< pair<pii,int> > q;
if(isFree[S.x][S.y]) {
cost[S.x][S.y] = 0;
reached[S.x][S.y] = (1<<8) - 1;
for(int k = 0;k < 8;k++) {
q.push(mp(S,k));
}
}
pii v, w;
int dir;
while(!q.empty()) {
v = q.front().x;
dir = q.front().y;
q.pop();
for(int k = 0;k < 8;k++) {
int d = dir + k, c;
d -= d < 8 ? 0 : 8;
c = k < 4 ? k : k - 4;
if(k > 0 && !c) c = 4;
w = mp(v.x + dx[d],v.y + dy[d]);
if(isFree[w.x][w.y]) {
if(cost[w.x][w.y] > cost[v.x][v.y] + c) {
cost[w.x][w.y] = cost[v.x][v.y] + c;
reached[w.x][w.y] = 0;
reached[w.x][w.y] |= (1<<d);
q.push(mp(w,d));
} else
if(cost[w.x][w.y] == cost[v.x][v.y] + c && ((reached[w.x][w.y]>>d) & 1) == 0) {
reached[w.x][w.y] |= (1<<d);
q.push(mp(w,d));
}
}
}
}
return cost[D.x][D.y] == inf ? -1 : cost[D.x][D.y];
}
int main()
{
readData();
cout<<bf();
return 0;
}