Cod sursa(job #2194617)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 13 aprilie 2018 21:31:15
Problema Portal3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("portal3.in");
ofstream fout("portal3.out");

int t;

struct info
{
    int x;
    int y;
};
int f(info a,info b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}
int n,m;
info v[10][10];
bool viz[10];
int costt[10];

int best;

void bkt(int strat,info last,int cost)
{
    int cost_nou=cost+f(last,{n,m});
    if(cost_nou<best)
        best=cost_nou;
    for(int i=1;i<=3;i++)
        if(viz[i]==0)
        {
            viz[i]=1;
            for(int j=1;j<=2;j++)
                bkt(strat+1,v[i][3-j],cost+f(last,v[i][j])+costt[i]);
            viz[i]=0;
        }
}

int main()
{
    fin>>t;
    for(int nr_t=1;nr_t<=t;nr_t++)
    {
        fin>>n>>m;
        for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=2;j++)
                fin>>v[i][j].x>>v[i][j].y;
            fin>>costt[i];
        }
        best=f({0,0},{n,m});
        bkt(0,{0,0},0);
        fout<<best<<"\n";
    }
    return 0;
}