Cod sursa(job #2296555)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 4 decembrie 2018 19:48:04
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.9 kb
#include <bits/stdc++.h>
#define Dim 505
#define Max 1000009
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int N,M,C[Dim][Dim],Si,Sj,Fi,Fj;
int Ans[Dim][Dim],info;
int dx[]={0,-1,1,0,0,-1,-1,1,1},dy[]={0,0,0,-1,1,-1,1,-1,1};
stack < pair < int,int > > stv;
bool stop=0;

int OK(int coordx,int coordy)
{
    if(coordx<=N&&coordy<=M&&coordx>=1&&coordy>=1&&C[coordx][coordy]==0)
        return 1;
    else return 0;
}

int Go(int nr1,int nr2)
{
    int input1=stv.top().first;
    int input2=stv.top().second;
    if(nr1==-1&&nr2==-1)
    {
        if(input1==-1&&input2==-1)return 0;
        else if(input1==1&&input2==1) return 4;
        else if(input1==-1&&input2==1) return 2;
        else if(input1==1&&input2==-1) return 2;
        else if(input1==-1&&input2==0) return 1;
        else if(input1==1&&input2==0) return 3;
        else if(input1==0&&input2==-1) return 1;
        else if(input1==0&&input2==1) return 3;
    }
    if(nr1==-1&&nr2==0)
    {
        if(input1==-1&&input2==-1)return 1;
        else if(input1==1&&input2==1) return 3;
        else if(input1==-1&&input2==1) return 1;
        else if(input1==1&&input2==-1) return 3;
        else if(input1==-1&&input2==0) return 0;
        else if(input1==1&&input2==0) return 4;
        else if(input1==0&&input2==-1) return 2;
        else if(input1==0&&input2==1) return 2;
    }
    if(nr1==-1&&nr2==1)
    {
        if(input1==-1&&input2==-1)return 2;
        else if(input1==1&&input2==1) return 2;
        else if(input1==-1&&input2==1) return 0;
        else if(input1==1&&input2==-1) return 4;
        else if(input1==-1&&input2==0) return 1;
        else if(input1==1&&input2==0) return 3;
        else if(input1==0&&input2==-1) return 3;
        else if(input1==0&&input2==1) return 1;
    }
    if(nr1==0&&nr2==-1)
    {
        if(input1==-1&&input2==-1)return 1;
        else if(input1==1&&input2==1) return 3;
        else if(input1==-1&&input2==1) return 3;
        else if(input1==1&&input2==-1) return 1;
        else if(input1==-1&&input2==0) return 2;
        else if(input1==1&&input2==0) return 2;
        else if(input1==0&&input2==-1) return 0;
        else if(input1==0&&input2==1) return 4;
    }
    if(nr1==0&&nr2==1)
    {
        if(input1==-1&&input2==-1)return 3;
        else if(input1==1&&input2==1) return 1;
        else if(input1==-1&&input2==1) return 1;
        else if(input1==1&&input2==-1) return 3;
        else if(input1==-1&&input2==0) return 2;
        else if(input1==1&&input2==0) return 2;
        else if(input1==0&&input2==-1) return 4;
        else if(input1==0&&input2==1) return 0;
    }
    if(nr1==1&&nr2==1)
    {
        if(input1==-1&&input2==-1)return 4;
        else if(input1==1&&input2==1) return 0;
        else if(input1==-1&&input2==1) return 2;
        else if(input1==1&&input2==-1) return 2;
        else if(input1==-1&&input2==0) return 3;
        else if(input1==1&&input2==0) return 1;
        else if(input1==0&&input2==-1) return 3;
        else if(input1==0&&input2==1) return 1;
    }
    if(nr1==1&&nr2==0)
    {
        if(input1==-1&&input2==-1)return 3;
        else if(input1==1&&input2==1) return 1;
        else if(input1==-1&&input2==1) return 3;
        else if(input1==1&&input2==-1) return 1;
        else if(input1==-1&&input2==0) return 4;
        else if(input1==1&&input2==0) return 0;
        else if(input1==0&&input2==-1) return 2;
        else if(input1==0&&input2==1) return 2;
    }
    if(nr1==1&&nr2==-1)
    {
        if(input1==-1&&input2==-1)return 2;
        else if(input1==1&&input2==1) return 2;
        else if(input1==-1&&input2==1) return 4;
        else if(input1==1&&input2==-1) return 0;
        else if(input1==-1&&input2==0) return 3;
        else if(input1==1&&input2==0) return 1;
        else if(input1==0&&input2==-1) return 3;
        else if(input1==0&&input2==1) return 1;
    }
}

void DFS(int x,int y,int mod1,int mod2)
{
    int l=x+mod1;
    int c=y+mod2;
    //cout<<x<<" "<<y<<" "<<C[x][y]<<" "<<l<<" "<<c<<" "<<C[l][c]<<'\n';
    if(OK(l,c))
    {
        info=Go(mod1,mod2);
        if(Ans[x][y]+info>=Ans[l][c]) return;
        else
        {
            Ans[l][c]=Ans[x][y]+info;
            //cout<<l<<" "<<c<<" "<<info<<" "<<Ans[x][y]<<" "<<Ans[l][c]<<'\n';;
            stv.push(make_pair(mod1,mod2));
        }
    }else return;
    for(int i=1;i<=8;i++)
        DFS(l,c,dx[i],dy[i]);
    stv.pop();
}

int main()
{
    f>>N>>M>>Si>>Sj>>Fi>>Fj;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
    {
        f>>C[i][j];
        Ans[i][j]=Max;
    }
    Ans[Si][Sj]=0;
    if(Si==Fi&&Sj==Fj)
    {
        g<<0;
        stop=1;
    }
    else
    {
       for(int i=1;i<=8;i++)
       {
           stv.push(make_pair(dx[i],dy[i]));

               DFS(Si,Sj,dx[i],dy[i]);

       }
       g<<Ans[Fi][Fj];
    }
    return 0;
}