Cod sursa(job #2359356)

Utilizator DavidDragulinDragulin David DavidDragulin Data 28 februarie 2019 19:54:13
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <bits/stdc++.h>

using namespace std;

#define inf INT_MAX
#define mp make_pair
#define f first
#define s second
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
InParser fin("car.in");
ofstream fout("car.out");
const int N=509;
int vx[]= {-1,-1,0,1,1,1,0,-1},vy[]= {0,1,1,1,0,-1,-1,-1},a[N][N],d[8][N][N];
int n,m,xi,yi,xf,yf,i,j;
queue <pair<int,pair<int,int> > > q;
void bordare()
{
    for(int i=0; i<=n+1; i++)
        a[i][0]=a[i][m+1]=1;
    for(int i=0; i<=m+1; i++)
        a[0][i]=a[n+1][i]=1;
}
void read()
{
    fin>>n>>m;
    fin>>xi>>yi>>xf>>yf;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            fin>>a[i][j];
}
void solve()
{
    int dir0[]= {0,1,2,3,4,3,2,1};
    int dir1[]= {1,0,1,2,3,4,3,2};
    int dir2[]= {2,1,0,1,2,3,4,3};
    int dir3[]= {3,2,1,0,1,2,3,4};
    int dir4[]= {4,3,2,1,0,1,2,3};
    int dir5[]= {3,4,3,2,1,0,1,2};
    int dir6[]= {2,3,4,3,2,1,0,1};
    int dir7[]= {1,2,3,4,3,2,1,0};
    bordare();
    for(int p=0; p<8; p++)
        for(i=1; i<=n; i++)
            for(j=1; j<=m; j++)
                d[p][i][j]=inf;
    for(int i=0; i<8; i++)
        if(!a[xi+vx[i]][yi+vy[i]])
            q.push(mp(i,mp(xi+vx[i],yi+vy[i]))),d[i][xi+vx[i]][yi+vy[i]]=0;
    while(!q.empty())
    {
        int dir=q.front().f;
        int x=q.front().s.f;
        int y=q.front().s.s;
        q.pop();
        for(int i=0; i<8; i++)
        {
            if(a[x+vx[i]][y+vy[i]])
                continue;
            int dist;
            if(dir==0)
                dist=dir0[i];
            if(dir==1)
                dist=dir1[i];
            if(dir==2)
                dist=dir2[i];
            if(dir==3)
                dist=dir3[i];
            if(dir==4)
                dist=dir4[i];
            if(dir==5)
                dist=dir5[i];
            if(dir==6)
                dist=dir6[i];
            if(dir==7)
                dist=dir7[i];
            if(d[i][x+vx[i]][y+vy[i]]>d[dir][x][y]+dist)
            {
                d[i][x+vx[i]][y+vy[i]]=d[dir][x][y]+dist;
                q.push(mp(i,mp(x+vx[i],y+vy[i])));
            }
        }
    }
    int ans=inf;
    for(int i=0;i<8;i++)
        ans=min(ans,d[i][xf][yf]);
    if(ans==inf)
        fout<<-1;
    else
        fout<<ans;
}
int main()
{
    read();
    solve();
    return 0;
}