Cod sursa(job #2868821)

Utilizator mateitudordmDumitru Matei mateitudordm Data 11 martie 2022 10:49:01
Problema Medie Scor 0
Compilator cpp-64 Status done
Runda lacuricodurimedie Marime 2.27 kb
#include <fstream>
#include <queue>
#define nmax 101

using namespace std;

ifstream cin ("lacuri.in");
ofstream cout ("lacuri.out");

int n, mat[nmax + 1][nmax + 1], c[nmax + 1][nmax + 1], dirx[] = {1, -1, 0, 0}, diry[] = {0, 0, 1, -1}, len, ok, sx, sy, cn;
pair<int, int> memo[nmax + 1][nmax + 1], sol[nmax * nmax + 1];
queue<pair<int, int>> q;

void dfs (int x, int y)
{
    for (int i = 0; i < 4; i++)
        if (c[x + dirx[i]][y + diry[i]] == 1)
            c[x + dirx[i]][y + diry[i]] = 0, dfs (x + dirx[i], y + diry[i]);
    if (! (x >= sx && x <= sx + len - 1 && y >= sy && y <= sy + len - 1))
        ok = 1;
    else
        cn++;
}

void bfs()
{
    int x, y, ax, ay, i;
    q.push ({1, 1});
    memo[1][1] = {1, 1};
    mat[1][1] = 1;
    while (!q.empty())
    {
        x = q.front().first, y = q.front().second;
        q.pop();
        for (i = 0; i < 4; i++)
        {
            ax = x + dirx[i], ay = y + diry[i];
            if (ax >= 1 && ay >= 1 && ax <= n && ay <= n && mat[ax][ay] == 0)
            {
                mat[ax][ay] = 1;
                memo[ax][ay] = {x, y};
                q.push ({ax, ay});
            }
        }
    }
}

int main()
{
    int cnt = 0, i, j, col, tot = 0, p = 0;
    pair<int, int> x;
    cin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            cin >> mat[i][j], c[i][j] = mat[i][j];
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (c[i][j] == 1)
            {
                tot++;
                ok = 0, len = 0;
                for (col = j; col <= n && c[i][col] == 1; col++)
                    len++;
                c[i][j] = 0;
                sx = i, sy = j, cn = 0;
                dfs (i, j);
                if (ok == 0 && cn == len * len)
                    cnt++;
            }
    cout << cnt << '\n';
    if (cnt == tot && (! (cnt == 1 && mat[1][1] == 1)))
    {
        bfs();
        x.first = x.second = n;
        while (x.first != 1 || x.second != 1)
        {
            sol[++p] = x;
            x = memo[x.first][x.second];
        }
        cout << 1 << " " << 1 << '\n';
        for (i = p; i >= 1; i--)
            cout << sol[i].first << " " << sol[i].second << '\n';
    }
    return 0;
}