Cod sursa(job #2233020)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 21 august 2018 21:43:34
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <stdlib.h>
#define mx 505
#define inf 1e9
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int n,m, xi,yi, xf,yf, a[mx][mx], c[mx][mx][8];
int dx[]={-1, -1, -1, 0, 1, 1, 1, 0};
int dy[]={-1, 0,  1,  1, 1, 0, -1, -1};
struct T{
    int a,b,c;
};
queue <T> q;

void bordare()
{
    int i;
    for(i=1; i<=n+1; i++)
    {a[i][0]=1; a[i][m+1]=1;}
    for(i=1; i<=m+1; i++)
    {a[0][i]=1; a[n+1][i]=1;}
}

void citire()
{
    int i,j,k;
    f>>n>>m>>xi>>yi>>xf>>yf;
    for(i=1; i<=n; i++)
    for(j=1; j<=m; j++)
        f>>a[i][j];

    for(i=1; i<=n; i++)
    for(j=1; j<=m; j++)
        for(k=0; k<8; k++)
            c[i][j][k]=inf;
}

void bfs(int i, int j)
{
    int x,y,xx,yy, k, cost, stare, st;
    for(k=0; k<8; k++)
    {
        q.push({i,j,k});
        c[i][j][k]=0;
    }
    while(!q.empty())
    {
        x=q.front().a;
        y=q.front().b;

        stare=q.front().c;
        q.pop();

        if(x==xf && y==yf)
            {g<<c[x][y][stare]; return;}
        //mergi in aceeasi directie
        xx=x+dx[stare]; yy=y+dy[stare];
        if(a[xx][yy]==0 && c[xx][yy][stare]>c[x][y][stare])
            {c[xx][yy][stare]=c[x][y][stare];
             q.push({xx,yy,stare});}
        //stai pe loc si schimba directia
        st=(stare+1)%8;
        if(c[x][y][st]>c[x][y][stare]+1)
            {c[x][y][st]=c[x][y][stare]+1;
            q.push({x,y,st});}
        st=(stare+7)%8;
        if(c[x][y][st]>c[x][y][stare]+1)
            {c[x][y][st]=c[x][y][stare]+1;
            q.push({x,y,st});}
    }
}

int main()
{
    bordare();
    citire();
    bfs(xi,yi);
    f.close();
    g.close();
    return 0;
}