Pagini recente » Cod sursa (job #2263181) | Rating Roman Roberto (Robertwow) | Cod sursa (job #2240884) | Cod sursa (job #728464) | Cod sursa (job #404828)
Cod sursa(job #404828)
#include <fstream>
#include <stack>
using namespace std;
const int MAX_N = 505;
const int INF = 0x3f3f3f3f;
ifstream fin ("car.in");
ofstream fout ("car.out");
const int dx[] = {-1,-1, 0, 1, 1, 1, 0,-1},
dy[] = { 0, 1, 1, 1, 0,-1,-1,-1};
int N, M, Xs, Ys, Xf, Yf, A[MAX_N][MAX_N];
int D[(1 << 21) + 4];
stack <int> Q[2];
inline int code(int i, int j, int dir)
{
return ((dir << 18) + (i << 9) + j);
}
void citire()
{
fin >> N >> M >> Xs >> Ys >> Xf >> Yf;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
fin >> A[i][j];
}
bool expand(int ant)
{
int j = (ant & 511), i = ((ant >> 9) & 511), dir = (ant >> 18);
int act = code(i, j, (dir+1)&7);
if(D[act] > D[ant]+1)
{
D[act] = D[ant]+1;
Q[D[act]&1].push(act);
}
act = code(i, j, (dir+7)&7);
if(D[act] > D[ant]+1)
{
D[act] = D[ant]+1;
Q[D[act]&1].push(act);
}
i += dx[dir], j += dy[dir];
if(i < 1 || i > N || j < 1 || j > M || A[i][j]) return 0;
if(i == Xf && j == Yf) return 1;
act = code(i, j, dir);
if(D[act] > D[ant])
{
D[act] = D[ant];
Q[D[act] & 1].push(act);
}
return 0;
}
void solve()
{
memset(D, INF, sizeof D);
for(int i = 0; i < 8; ++i)
{
int act = code(Xs, Ys, i);
Q[0].push(act);
D[act] = 0;
}
int Sol = 0;
while(!Q[0].empty() || !Q[1].empty())
{
while(!Q[Sol&1].empty())
{
int act = Q[Sol & 1].top();
Q[Sol & 1].pop();
if(expand(act))
{
fout << Sol;
return;
}
}
++Sol;
}
}
int main()
{
citire();
solve();
}