Pagini recente » Cod sursa (job #601912) | Cod sursa (job #679927) | Cod sursa (job #184364) | Cod sursa (job #642854) | Cod sursa (job #990798)
Cod sursa(job #990798)
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;
const string file = "car";
const string infile = file + ".in";
const string outfile = file + ".out";
const int INF = 0x3f3f3f3f;
int N, M;
int Si, Sj;
int Fi, Fj;
#define MAXN 501
int A[MAXN][MAXN];
int dist[MAXN][MAXN][8];
int used[MAXN][MAXN][8];
int minCost = INF;
struct Car
{
int x;
int y;
int dir;
int dis;
Car(int x, int y, int dir, int dis)
{
this->x = x;
this->y = y;
this->dir = dir;
this->dis = dis;
}
};
queue<Car> Q[3];
int dY[] = {0, 1 ,1 ,1, 0, -1, -1, -1};
int dX[] = {-1, -1, 0, 1, 1, 1, 0, -1};
void Dijkstra()
{
int k = 0;
for(int i = 0; i < 8; i++)
{
Q[0].push(Car(Si, Sj, i, 0));
dist[Si][Sj][i] = 0;
used[Si][Sj][i] = 1;
}
while(true)
{
if(minCost != INF)
break;
if(Q[0].empty() == true && Q[1].empty() == true && Q[2].empty() == true)
break;
while(Q[k%3].empty() == false)
{
Car c = Q[k%3].front();
Q[k%3].pop();
if(c.x == Fi && c.y == Fj)
{
minCost = min(minCost, dist[c.x][c.y][c.dir]);
}
for(int i = -2; i <= 2; i++)
{
int newDir = (c.dir + i) % 8;
newDir = newDir < 0 ? newDir + 8 : newDir;
int newX = c.x + dX[newDir];
int newY = c.y + dY[newDir];
if(!( 1 <= newX && newX <= N && 1<= newY && newY <= M))
continue;
if(A[newX][newY] == 1)
continue;
if(dist[newX][newY][newDir] > dist[c.x][c.y][c.dir] + abs(i))
{
dist[newX][newY][newDir] = dist[c.x][c.y][c.dir] + abs(i);
if(used[newX][newY][newDir] == 0)
{
used[newX][newY][newDir] = 1;
Q[(k+abs(i))%3].push(Car(newX, newY, newDir, dist[newX][newY][newDir]));
}
}
}
}
k++;
}
}
int main()
{
fstream fin(infile.c_str(), ios::in);
fin >> N >> M;
fin >> Si >> Sj;
fin >> Fi >> Fj;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
for(int k = 0; k < 8; k++)
{
dist[i][j][k] = INF;
}
}
}
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
fin >> A[i][j];
}
}
fin.close();
Dijkstra();
fstream fout(outfile.c_str(), ios::out);
if(minCost != INF)
{
fout << minCost << "\n";
}
else
{
fout << "-1\n";
}
fout.close();
}