Cod sursa(job #865878)

Utilizator ELHoriaHoria Cretescu ELHoria Data 27 ianuarie 2013 11:17:46
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <queue>
#define getCode(x,y,d) (x + (y<<9) + (d<<18))
#define pii pair<int,int>
#define x first
#define y second

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][8];
pii S, D;
queue<int> q[2];
 
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++) {
            for(int k = 0;k < 8;k++) {
                cost[i][j][k] = inf;   
            }
            isFree[i][j] ^= 1;
        }
    }
	int line = 0;
    if(isFree[S.x][S.y]) {
        for(int k = 0;k < 8;k++) {
            cost[S.x][S.y][k] = 0;
			q[line].push(getCode(S.x,S.y,k));
        }
    }
	pii v, w;
	for(int k;!q[0].empty() || !q[1].empty();line = 1 - line) {
		while(!q[line].empty()) {
			v.x = q[line].front() & (NMAX - 1);
			v.y = (q[line].front()>>9) & (NMAX - 1);
			k = q[line].front()>>18;
			q[line].pop();
			if(v == D) {
				return cost[v.x][v.y][k];
			}
			w.x = v.x + dx[k];
			w.y = v.y + dy[k];
			if(isFree[w.x][w.y] && cost[w.x][w.y][k] > cost[v.x][v.y][k]) {
				cost[w.x][w.y][k] = cost[v.x][v.y][k];
				q[line].push(getCode(w.x,w.y,k));
			}
			int Left = (k - 1 + 8) & 7;
			int Right = (k + 1) & 7;
			if(cost[v.x][v.y][Left] > cost[v.x][v.y][k] + 1) {
				cost[v.x][v.y][Left] = cost[v.x][v.y][k] + 1;
				q[1 - line].push(getCode(v.x,v.y,Left));
			}
			if(cost[v.x][v.y][Right] > cost[v.x][v.y][k] + 1) {
				cost[v.x][v.y][Right] = cost[v.x][v.y][k] + 1;
				q[1 - line].push(getCode(v.x,v.y,Right));
			}
		}
	}
	return -1;
}
 
int main()
{
    readData();
    cout<<bf();
    return 0;
}