Cod sursa(job #1464127)

Utilizator DenisacheDenis Ehorovici Denisache Data 22 iulie 2015 13:30:53
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <queue>
#include <set>
#include <unordered_map>
#include <functional>
//#include <conio.h>
#define pb push_back
#define mp make_pair
#define MOD 9901
#define newl printf("\n")
#define NMAX 505
#define nst (nod<<1)
#define ndr (nst+1)
#define vi vector<int>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int INF = (1<<30);
int n,m,xs,ys,xf,yf,mat[NMAX][NMAX],ans=INF;
bool used[NMAX][NMAX];
vector < pair<int,int> > L[3];
void updateCoord(int &i,int &j,int dir)
{
    if (dir>7) dir-=8;
    else if (dir<0) dir+=8;

    if (dir==0) i--;
    else if (dir==1) i--,j++;
    else if (dir==2) j++;
    else if (dir==3) i++,j++;
    else if (dir==4) i++;
    else if (dir==5) i++,j--;
    else if (dir==6) j--;
    else if (dir==7) i--,j--;
}
void check(int i,int j,int dir,int currentCost,int totalCost)
{
    if (dir>7) dir-=8;
    else if (dir<0) dir+=8;
    if (mat[i][j]==0 && i<=n && j<=m && i>0 && j>0)
    {
        L[currentCost].pb(mp((i<<9)+j+(dir<<18),totalCost+currentCost));
        used[i][j]=true;
    }
    if (i==xf && j==yf && totalCost+currentCost<ans)
        ans=totalCost+currentCost;
}
int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    scanf("%d %d",&n,&m);
    scanf("%d %d %d %d",&xs,&ys,&xf,&yf);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&mat[i][j]);
    if (mat[xf][yf]==1)
    {
        printf("-1");
        return 0;
    }
    for (int dir=0;dir<8;dir++)
        L[0].pb(mp((xs<<9)+ys+(dir<<18),0));
    int currentCost=0;
    while (L[0].size()+L[1].size()+L[2].size()>0)
    {
        while (L[currentCost%3].size()>0)
        {
            int x=L[currentCost%3].back().fi,totalCost=L[currentCost%3].back().se;
            L[currentCost%3].pop_back();
            int i=(x>>9)&511,j=x&511,dir=x>>18;
            int auxi=i,auxj=j;
            updateCoord(i,j,dir);
            check(i,j,dir,0,totalCost);
            i=auxi,j=auxj;
            updateCoord(i,j,dir+2);
            check(i,j,dir+2,2,totalCost);
            i=auxi,j=auxj;
            updateCoord(i,j,dir-2);
            check(i,j,dir-2,2,totalCost);
            i=auxi,j=auxj;
            updateCoord(i,j,dir+1);
            check(i,j,dir+1,1,totalCost);
            i=auxi,j=auxj;
            updateCoord(i,j,dir-1);
            check(i,j,dir-1,1,totalCost);
        }
        currentCost++;
    }
    if (ans==INF) printf("-1");
    else printf("%d",ans);
    return 0;
}