Cod sursa(job #2929018)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 24 octombrie 2022 14:21:21
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#import <algorithm>
#import <vector>
#import <map>
#import <set>
#import <deque>
#import <queue>
#import <cassert>
//#import <cmath>
#import <cstring>
#import <cctype>
#import <cstdlib>
#import <stack>
#import<unordered_map>
#define lene using std::cin;using std::cout
const int mod=8;
const int dl[]={-1,-1, 0, 1, 1, 1, 0,-1};
const int dc[]={ 0, 1, 1, 1, 0,-1,-1,-1};
struct cord
{
    int y,x;
    cord(){}
    cord(int _y,int _x): y(_y), x(_x){}
};
std::ifstream& operator >>(std::ifstream &is,cord& a)
{
    is>>a.y>>a.x;
    return is;
}
///exact aceeasi denumire cu notele de ascultare de la istorie
struct patru
{
    int dir,sum;
    cord poz;
    patru(){}
    patru(cord _poz,int _dir,int _sum):poz(_poz), dir(_dir), sum(_sum){}
};
bool in(cord a,int n,int m)
{
    if(a.x<=0 || a.y<=0 || a.y>n || a.x>m)return 0;
    return 1;
}
int add(int x,int v)
{
    x+=v;
    if(x<0)x+=mod;
    return x%mod;
}
#define el(y,x) *min_element(rez[y][x].begin(),rez[y][x].end())
#define e(y,x) rez[y][x]
main()
{
    std::ifstream cin("car.in");
    std::ofstream cout("car.out");
    int n,m;
    cin>>n>>m;
    std::vector<std::vector<int>>ok(n+1,std::vector<int>(m+1));
    std::vector<std::vector<std::vector<int>>>rez(n+1,std::vector<std::vector<int>>(m+1,std::vector<int>(8,2e9)));
    cord from,to;
    cin>>from>>to;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>ok[i][j];
        }
    }
    std::deque<patru>d;
    for(int i=0;i<8;i++)
    {
        d.push_back(patru(from,i,0));
        rez[from.y][from.x][i]=0;
    }
    while(!d.empty())
    {
        patru old=d.front();
        d.pop_front();
        if(old.sum!=rez[old.poz.y][old.poz.x][old.dir])
        {
            continue;
        }
        ///merg inainte
        {
            cord nou(old.poz.y+dl[old.dir],old.poz.x+dc[old.dir]);
            if(in(nou,n,m) && !ok[nou.y][nou.x] && old.sum<rez[nou.y][nou.x][old.dir])
            {
                rez[nou.y][nou.x][old.dir]=old.sum;
                d.push_front(patru(nou,old.dir,old.sum));
            }
        }
        ///-1
        {
            int nou=add(old.dir,-1);
            if(old.sum+1<rez[old.poz.y][old.poz.x][nou])
            {
                rez[old.poz.y][old.poz.x][nou]=old.sum+1;
                d.push_back(patru(old.poz,nou,old.sum+1));
            }
        }

        ///1
        {
            int nou=add(old.dir,1);
            if(old.sum+1<rez[old.poz.y][old.poz.x][nou])
            {
                rez[old.poz.y][old.poz.x][nou]=old.sum+1;
                d.push_back(patru(old.poz,nou,old.sum+1));
            }
        }
    }
    cout<<el(to.y,to.x);

}