Cod sursa(job #2839829)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 26 ianuarie 2022 17:28:14
Problema Barbar Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

ifstream in ("poarta.in");
ofstream out ("poarta.out");

int numarare(pair<int, int> start, pair<int, int> fin)
{
    int x = abs(start.first - fin.first) + 1;
    int y = abs(start.second - fin.second) + 1;

    vector< vector<int> > M(x, vector<int> (y, 0));
    M[0][0] = 1;
    for (int i = 0; i < x; i++)
        for (int j = 0; j < y; j++)
        {
            if (j - 1 >= 0)
                M[i][j] += M[i][j - 1];
            if (i - 1 >= 0)
                M[i][j] += M[i - 1][j];
        }
    return M[x - 1][y -1];
}

int main()
{
    int N, M, K;
    pair<int, int> start, fin;
    in>> N >> M >> K;
    in>> start.first >> start.second;
    in>> fin.first >> fin.second;
    vector< pair<int, int> > porti (K);

    for (int i = 0; i < K; i++)
    {
        in>> porti[i].first >> porti[i].second;
    }
    int d = abs(start.first - fin.first) + abs(start.second - fin.second), dmin = N * M + 1;
    if (d < dmin)
        dmin = d;

    int dminS = N * M + 1, dminF = N * M + 1;

    for (int i = 0; i < K; i++)
    {
        d = abs(start.first - porti[i].first) + abs(start.second - porti[i].second);
        if (d < dminS)
            dminS = d;
    }
    for (int i = 0; i < K; i++)
    {
        d = abs(fin.first - porti[i].first) + abs(fin.second - porti[i].second);
        if (d < dminF)
            dminF = d;
    }
    if (dmin < dminS + dminF + 1)
    {
        out<< dmin << "\n";
        out<< numarare(start, fin);
    }
    else
    {
        out<< dminS + dminF + 1 << "\n";
        int s1 = 0, s2 = 0;

        for (int i = 0; i < K; i++)
        {
            d = abs(start.first - porti[i].first) + abs(start.second - porti[i].second);

            if (d == dminS)
            s1 += numarare(start, porti[i]);
        }

        for (int i = 0; i < K; i++)
        {
            d = abs(fin.first - porti[i].first) + abs(fin.second - porti[i].second);

            if (d == dminF)
                s2 += numarare(fin, porti[i]);
        }

        if (dmin == dminS + dminF + 1)
            out<< s1 * s2 + dmin;
        else
            out<< s1 * s2;
    }


    in.close();
    out.close();
    return 0;
}