Cod sursa(job #2634977)

Utilizator loraclorac lorac lorac Data 12 iulie 2020 20:23:53
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
const int dx[]={-1, 0, 1,1,1,0,-1,-1};
const int dy[]={-1,-1,-1,0,1,1, 1, 0};
bool ok[10][505][505];
struct Op
{int dir; int x; int y; int cost;};
int n,m,xs,ys,xf,yf,fake;
bool good(int d,int x,int y)
{
    if(1<=x and x<=n and 1<=y and y<=m and ok[d][x][y]==0)
        return true;
    return false;
}
queue<Op> q;
int main()
{
    in>>n>>m>>xs>>ys>>xf>>yf;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    {
        in>>fake;
        if(fake) for(int d=0;d<8;++d)
            ok[d][i][j]=1;
    }
    for(int d=0;d<8;++d)
    {
        int xx=xs,yy=ys;
        while(good(d,xx,yy))
            q.push({d,xx,yy,0}),ok[d][xx][yy]=1,xx+=dx[d],yy+=dy[d];
    }
    while(!q.empty())
    {
        int dir=q.front().dir;
        int x=q.front().x;
        int y=q.front().y;
        int cost=q.front().cost;
        q.pop();
        if(x==xf and y==yf) {out<<cost<<'\n';return 0;}
        int d1=dir-1,d2=dir+1;
        if(d1<0) d1+=8;
        if(d2>=8) d2-=8;
        int xx=x,yy=y;
        while(good(d1,xx,yy))
        {
            if(xx==xf and yy==yf) {out<<cost+1<<'\n';return 0;}
            q.push({d1,xx,yy,cost+1}),ok[d1][xx][yy]=1,xx+=dx[d1],yy+=dy[d1];
        }
        xx=x;
        yy=y;
        while(good(d2,xx,yy))
        {
            if(xx==xf and yy==yf) {out<<cost+1<<'\n';return 0;}
            q.push({d2,xx,yy,cost+1}),ok[d2][xx][yy]=1,xx+=dx[d2],yy+=dy[d2];
        }
    }
    out<<-1<<'\n';
    return 0;
}