Pagini recente » Cod sursa (job #2461790) | Cod sursa (job #648053) | Cod sursa (job #849694) | Cod sursa (job #486628) | Cod sursa (job #990847)
Cod sursa(job #990847)
#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 minCost = INF;
struct Nod
{
int lista;
int x;
int y;
int dir;
Nod*next;
Nod*prev;
Nod(int x = 0, int y = 0, int dir = 0, int lista = -1)
{
this->x = x;
this->y = y;
this->lista = lista;
this->dir = dir;
}
};
struct Lista
{
Nod begin;
int size;
Lista()
{
begin.next = &begin;
begin.prev = &begin;
size = 0;
}
Nod* popFront()
{
if(size == 0)
return NULL;
Nod * r = begin.next;
r->next->prev = r->prev;
r->prev->next = r->next;
size--;
return r;
}
void deleteNod(Nod* nod)
{
nod->next->prev = nod->prev;
nod->prev->next = nod->next;
nod->lista = -1;
size--;
}
void pushBack(Nod* nod)
{
nod->next = &begin;
nod->prev = begin.prev;
nod->prev->next = nod;
nod->next->prev = nod;
size++;
}
};
struct Car
{
int x;
int y;
int dir;
int dis;
Car(int x, int y, int dir)
{
this->x = x;
this->y = y;
this->dir = dir;
}
};
Lista lists[2];
Nod nods[MAXN][MAXN][8];
queue<Car> Q[2];
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));
nods[Si][Sj][i].lista = 0;
lists[0].pushBack(&nods[Si][Sj][i]);
dist[Si][Sj][i] = 0;
}
while(true)
{
if(minCost != INF)
break;
/*
if(Q[0].empty() == true && Q[1].empty() == true)
break;
*/
if(lists[0].size == 0 && lists[1].size == 0)
break;
while(lists[k%2].size != 0)
//while(Q[k%2].empty() == false)
{
//Car c = Q[k%2].front();
//Q[k%2].pop();
Nod c = *lists[k%2].popFront();
if(c.x == Fi && c.y == Fj)
{
minCost = min(minCost, dist[c.x][c.y][c.dir]);
}
for(int i = -1; i <= 1; i += 2)
{
int newDir = (c.dir + i) % 8;
newDir = newDir < 0 ? newDir + 8 : newDir;
if(dist[c.x][c.y][newDir] > dist[c.x][c.y][c.dir] + abs(i))
{
dist[c.x][c.y][newDir] = dist[c.x][c.y][c.dir] + abs(i);
//Q[(k+abs(i))%2].push(Car(c.x, c.y, newDir));
if(nods[c.x][c.y][newDir].lista != -1)
lists[nods[c.x][c.y][newDir].lista].deleteNod(&nods[c.x][c.y][newDir]);
nods[c.x][c.y][newDir].lista = (k + abs(i))%2;
lists[(k + abs(i))%2].pushBack(&nods[c.x][c.y][newDir]);
}
}
for(int i = -1; i <= 1; 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);
//Q[(k+abs(i))%2].push(Car(newX, newY, newDir));
if(nods[newX][newY][newDir].lista != -1)
lists[nods[newX][newY][newDir].lista].deleteNod(&nods[newX][newY][newDir]);
nods[newX][newY][newDir].lista = (k + abs(i))%2;
lists[(k + abs(i))%2].pushBack(&nods[newX][newY][newDir]);
}
}
}
k++;
}
}
fstream fin(infile.c_str(), ios::in);
const int BUFLEN = 4084;
char buffer[BUFLEN];
int p;
int nextInt()
{
int result = 0;
while(!( '0' <=buffer[p] && buffer[p] <= '9'))
{
if(++p >= BUFLEN)
{
fin.read(buffer, BUFLEN);
p = 0;
}
}
while( '0' <=buffer[p] && buffer[p] <= '9')
{
result *= 10;
result += buffer[p] - '0';
if(++p >= BUFLEN)
{
fin.read(buffer, BUFLEN);
p = 0;
}
}
return result;
}
int main()
{
p = BUFLEN;
N = nextInt();
M = nextInt();
Si = nextInt();
Sj = nextInt();
Fi = nextInt();
Fj = nextInt();
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
for(int k = 0; k < 8; k++)
{
nods[i][j][k] = Nod(i, j, k);
}
}
}
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++)
{
A[i][j] = nextInt();
}
}
fin.close();
Dijkstra();
fstream fout(outfile.c_str(), ios::out);
if(minCost != INF)
{
fout << minCost << "\n";
}
else
{
fout << "-1\n";
}
fout.close();
}