Pagini recente » Cod sursa (job #897334) | Cod sursa (job #881188)
Cod sursa(job #881188)
#include <fstream>
#include <queue>
#include <cstdlib>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int nmax= 500, cmax= 3, dmax= 8;
const int dx[8]= {-1, -1, 0, 1, 1, 1, 0, -1},
dy[8]= {0, 1, 1, 1, 0, -1, -1, -1};
int cst[dmax][dmax];
bool u[nmax+2][nmax+2][dmax];
inline int enc(int x, int y, int d){
return ((x<<12)+(y<<3)+d);
}
queue <int> q[cmax];
char *buffer;
void read_int(int &x){
while (*buffer<'0'|| *buffer>'9'){
++buffer;
}
x= 0;
while (*buffer>='0'&& *buffer<='9'){
x= 10*x+*buffer-'0';
++buffer;
}
}
void read_bool(bool &x){
while (*buffer!='0'&& *buffer!='1'){
++buffer;
}
x= *buffer-'0';
++buffer;
}
int main()
{
fin.seekg(0, ios::end);
int fs= fin.tellg();
fin.seekg(0, ios::beg);
buffer= (char*)malloc(fs);
fin.getline(buffer, fs, 0);
for (int i= 0; i<dmax; ++i){
for (int j= 0; j<dmax; ++j){
if (j<i){
cst[i][j]= cst[j][i];
}else if (i+8-j<j-i){
cst[i][j]= i+8-j;
}else{
cst[i][j]= j-i;
}
}
}
int n, m;
read_int(n); read_int(m);
int src_x, src_y, dest_x, dest_y;
read_int(src_x); read_int(src_y);
read_int(dest_x); read_int(dest_y);
for (int i= 1; i<=n; ++i){
for (int j= 1; j<=m; ++j){
read_bool(u[i][j][0]);
if (u[i][j][0]){
for (int k= 1; k<dmax; ++k){
u[i][j][k]= 1;
}
}
}
}
for (int i= 0; i<dmax; ++i){
for (int j= 0; j<=n+1; ++j){
u[j][0][i]= 1;
u[j][m+1][i]= 1;
}
for (int j= 1; j<=m; ++j){
u[0][j][i]= 1;
u[n+1][j][i]= 1;
}
}
for (int i= 0; i<dmax; ++i){
q[0].push(enc(src_x, src_y, i));
}
int aux, ind, x, y, d, xn, yn;
for (int i= 0; !(q[0].empty()&& q[1].empty()&& q[2].empty()); ++i){
ind= i%cmax;
while (q[ind].empty()==0){
aux= q[ind].front();
x= aux>>12, y= (aux>>3)&511, d= aux&7;
if (x==dest_x&& y==dest_y){
fout<<i<<"\n";
return 0;
}
q[ind].pop();
if (u[x][y][d]==0){
u[x][y][d]= 1;
for (int j= 0; j<dmax; ++j){
xn= x+dx[j], yn= y+dy[j];
if (cst[d][j]<cmax&& u[xn][yn][j]==0){
q[(ind+cst[d][j])%cmax].push(enc(xn, yn, j));
}
}
}
}
}
fout<<"-1\n";
return 0;
}