• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi
Zapytaj

Zadanie żywopłot, finał XXIII OI

Object Storage Arubacloud
0 głosów
224 wizyt
pytanie zadane 13 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 13 kwietnia 2023 przez pasjonat_algorytmiki
Mam problem z zadaniem żywopłot z finału XXIII OI: https://szkopul.edu.pl/problemset/problem/dABzva_j1-BvzKMsyxkuRoue/site/?key=statement

Nie wiem jak je zrobić, oprócz jakiegoś wykładniczego bruta na 25pkt.

Z góry dziękuję za pomoc i poświęcony czas!

1 odpowiedź

+1 głos
odpowiedź 13 kwietnia 2023 przez Whistleroosh Maniak (56,980 p.)
wybrane 14 kwietnia 2023 przez pasjonat_algorytmiki
 
Najlepsza
Taka prosta obserwacja. Załóżmy, że pola to wierzchołki w grafie. Jeśli jest przejście między 2 polami to jest krawędź między odpowiadającymi wierzchołkami w grafie. Dla poprawnego labiryntu jakiej postaci jest ten graf?
Pokaż 10 poprzednich komentarzy
komentarz 13 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
chwila chwila, da się chyba to O(N*M) zrobić! Bierzemy algorytm Prima, i modyfikujemy go tak jak Dijkstrę 0-1 robiąc na deque zamist kolejki priorytetowej / seta.
 komentarz 13 kwietnia 2023 przez Whistleroosh Maniak (56,980 p.)
No tak, i to jest wzorcówka
 komentarz 14 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 14 kwietnia 2023 przez pasjonat_algorytmiki

Napisałem taki kod:

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

enum Kierunek
{
    GORA, DOL, LEWO, PRAWO, BRAK
};

struct Pole
{
    int y;
    int x;
    Kierunek kier;
    int val;
};

int n = 0, m = 0, wyn_cis = 0, wyn_inne = 0;
char wczytany_znak;
vector<vector<int>> dp;
vector<vector<int>> krawedzie_gora;
vector<vector<int>> krawedzie_dol;
vector<vector<int>> krawedzie_lewo;
vector<vector<int>> krawedzie_prawo;
deque<Pole> Q;
vector<vector<bool>> czy_w_MST_pionowe;
vector<vector<bool>> czy_w_MST_poziome;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    dp.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        dp[i].assign(m+2,1e9);

    krawedzie_gora.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_gora[i].assign(m+2,0);

    krawedzie_dol.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_dol[i].assign(m+2,0);

    krawedzie_lewo.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_lewo[i].assign(m+2,0);

    krawedzie_prawo.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_prawo[i].assign(m+2,0);

    czy_w_MST_poziome.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        czy_w_MST_poziome[i].assign(m+1,false);

    czy_w_MST_pionowe.assign(n+1,{});
    for (int i = 1; i <= n; ++i)
        czy_w_MST_pionowe[i].assign(m+2,false);

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            cin >> wczytany_znak;
            if (wczytany_znak == 'T')
            {
                krawedzie_dol[i][j] = 1;
                krawedzie_gora[i+1][j] = 1;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> wczytany_znak;
            if (wczytany_znak == 'T')
            {
                krawedzie_prawo[i][j] = 1;
                krawedzie_lewo[i][j+1] = 1;
            }
        }
    }

    for (int j = 1; j <= m+1; ++j)
    {
        dp[1][j] = 0;
        Q.push_back({1,j,BRAK,0});
    }
    for (int j = 1; j <= m+1; ++j)
    {
        dp[n+1][j] = 0;
        Q.push_back({n+1,j,BRAK,0});
    }
    for (int i = 2; i <= n; ++i)
    {
        dp[i][1] = 0;
        Q.push_back({i,1,BRAK,0});
    }
    for (int i = 2; i <= n; ++i)
    {
         dp[i][m+1] = 0;
         Q.push_back({i,m+1,BRAK,0});
    }

    while(!Q.empty())
    {
        Pole spr = Q.front();
        Q.pop_front();
        if (spr.val > dp[spr.y][spr.x])
            continue;
        if (spr.kier != BRAK)
        {
            if (spr.kier == LEWO)
                czy_w_MST_poziome[spr.y][spr.x-1] = true;
            else if (spr.kier == PRAWO)
                czy_w_MST_poziome[spr.y][spr.x] = true;
            if (spr.kier == GORA)
                czy_w_MST_pionowe[spr.y-1][spr.x] = true;
            else if (spr.kier == DOL)
                czy_w_MST_pionowe[spr.y][spr.x] = true;
        }
        if (spr.y - 1 >= 1)
        {
            if (dp[spr.y-1][spr.x] == false)
            {
                if (krawedzie_gora[spr.y][spr.x] == 0)
                {
                    if (0 < dp[spr.y-1][spr.x])
                    {
                        dp[spr.y-1][spr.x] = 0;
                        Q.push_front({spr.y-1, spr.x,DOL, 0});
                    }
                }
                else
                {
                    if (1 < dp[spr.y-1][spr.x])
                    {
                        dp[spr.y-1][spr.x] = 1;
                        Q.push_back({spr.y-1, spr.x, DOL,1});
                    }
                }
            }
        }
        if (spr.y + 1 <= n+1)
        {
            if (krawedzie_dol[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y+1][spr.x])
                {
                    dp[spr.y+1][spr.x] = 0;
                    Q.push_front({spr.y+1, spr.x, GORA,0});
                }
            }
            else
            {
                if (1 < dp[spr.y+1][spr.x])
                {
                    dp[spr.y+1][spr.x] = 1;
                    Q.push_back({spr.y+1, spr.x, GORA,1});
                }
            }
        }
        if (spr.x - 1 >= 1)
        {
            if (krawedzie_lewo[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y][spr.x-1])
                {
                    dp[spr.y][spr.x-1] = 0;
                    Q.push_front({spr.y, spr.x-1, PRAWO,0});
                }
            }
            else
            {
                if (1 < dp[spr.y][spr.x-1])
                {
                    dp[spr.y][spr.x-1] = 1;
                    Q.push_back({spr.y, spr.x-1, PRAWO,1});
                }
            }
        }
        if (spr.x + 1 <= m+1)
        {
            if (krawedzie_prawo[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y][spr.x+1])
                {
                    dp[spr.y][spr.x+1] = 0;
                    Q.push_front({spr.y, spr.x+1, LEWO,0});
                }
            }
            else
            {
                if (1 < dp[spr.y][spr.x+1])
                {
                    dp[spr.y][spr.x+1] = 1;
                    Q.push_back({spr.y, spr.x+1, LEWO,1});
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (czy_w_MST_pionowe[i][j] == true)
            {
                if (krawedzie_dol[i][j] == 0)
                {
                    wyn_cis++;
                }
                else
                {
                    wyn_inne++;
                }
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (czy_w_MST_poziome[i][j] == true)
            {
                if (krawedzie_prawo[i][j] == 0)
                {
                    wyn_cis++;
                }
                else
                {
                    wyn_inne++;
                }
            }
        }
    }
    cout << wyn_cis+wyn_inne << ' ' << wyn_cis << '\n';

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (czy_w_MST_pionowe[i][j] == true)
                cout << 'Z';
            else
                cout << '.';
        }
        cout << '\n';
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (czy_w_MST_poziome[i][j] == true)
                cout << 'Z';
            else
                cout << '.';
        }
        cout << '\n';
    }

    return 0;
}

Mam gdzieś błąd, o ile robiłeś to zadanie, to wyślesz kod dający 100pkt, i napiszę sobie sprawdzarkę i sprawdzę co jest źle? Przechodzi wszystkie testy na wstępnym sprawdzaniu, ale wywala się w kilku testach właściwych. Wypisuje zamało z cisem.

1
 komentarz 14 kwietnia 2023 przez Whistleroosh Maniak (56,980 p.) 
#include <bits/stdc++.h>

typedef unsigned short us;
typedef unsigned long ul;
typedef long l;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const l INF = 1e9 + 9;
const l MOD = 1e9 + 7;
const l PRIME = 200003;
const ll L_INF = 1e18 + 1;
const double EPS = 10e-9;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second

using namespace std;

l n, m, all_cis, cis, all_tuja, tuja;
l group_size[1000005], leader[1000005];
vector<pair<l, l> > graph[2];
set<l> path[1000005];

l FIND(l v)
{
    if(leader[v] != v)
        leader[v] = FIND(leader[v]);

    return leader[v];
}

void UNION(l a, l b)
{
    l l_a = FIND(a);
    l l_b = FIND(b);

    if(group_size[l_a] > group_size[l_b])
    {
        group_size[l_a] += group_size[l_b];
        leader[l_b] = leader[l_a];
    }

    else
    {
        group_size[l_b] += group_size[l_a];
        leader[l_a] = leader[l_b];
    }
}

int main()
{
    cin >> n >> m;

    REP(n*m, i)
    {
        group_size[i+1] = 1;
        leader[i+1] = i+1;
    }

    FORE(1, n, i)
    {
        FORE(1, m-1, j)
        {
            char a;
            cin >> a;

            l pos = (i-1)*m+j;

            if(a == 'C')
            {
                graph[1].PB({pos, pos+1});
                all_cis++;
            }

            else
            {
                graph[0].PB({pos, pos+1});
                all_tuja++;
            }
        }
    }

    FORE(1, n-1, i)
    {
        FORE(1, m, j)
        {
            char a;
            cin >> a;

            l pos = (i-1)*m+j;

            if(a == 'C')
            {
                graph[1].PB({pos, pos+m});
                all_cis++;
            }

            else
            {
                graph[0].PB({pos, pos+m});
                all_tuja++;
            }
        }
    }

    for(auto v: graph[0])
    {
        if(FIND(v.FS) != FIND(v.SC))
        {
            UNION(v.FS, v.SC);
            path[v.FS].insert(v.SC);
            tuja++;
        }
    }

    for(auto v: graph[1])
    {
        if(FIND(v.FS) != FIND(v.SC))
        {
            UNION(v.FS, v.SC);
            path[v.FS].insert(v.SC);
            cis++;
        }
    }

    cout << (all_cis-cis) + (all_tuja-tuja) << " ";
    cout << all_cis-cis << "\n";

    FORE(1, n, i)
    {
        FORE(1, m-1, j)
        {
            l pos = (i-1)*m+j;

            if(path[pos].find(pos+1) != path[pos].end() || path[pos+1].find(pos) != path[pos+1].end())
                cout << ".";

            else
                cout << "Z";
        }

        cout << "\n";
    }

    FORE(1, n-1, i)
    {
        FORE(1, m, j)
        {
            l pos = (i-1)*m+j;

            if(path[pos].find(pos+m) != path[pos].end() || path[pos+m].find(pos) != path[pos+m].end())
                cout << ".";

            else
                cout << "Z";
        }

        cout << "\n";
    }
}

 

1
 komentarz 14 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 14 kwietnia 2023 przez pasjonat_algorytmiki

Przeszło, miałem jednego złego if-a.

Kod dający 100pkt, O(N*M), Algorytm Prima na Deque.

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

enum Kierunek
{
    GORA, DOL, LEWO, PRAWO, BRAK
};

struct Pole
{
    int y;
    int x;
    Kierunek kier;
    int val;
};

int n = 0, m = 0, wyn_cis = 0, wyn_inne = 0;
char wczytany_znak;
vector<vector<int>> dp;
vector<vector<int>> krawedzie_gora;
vector<vector<int>> krawedzie_dol;
vector<vector<int>> krawedzie_lewo;
vector<vector<int>> krawedzie_prawo;
deque<Pole> Q;
vector<vector<bool>> czy_w_MST_pionowe;
vector<vector<bool>> czy_w_MST_poziome;
vector<vector<bool>> visited;

int main()
{
    // O(N*M), MST, algorytm Prima na deque(zamiast kolejki priorytetowej / seta, bo wagi na krawedziach to 0 i 1, robimy tak jak Dijkstra 0-1 na deque)
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    dp.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        dp[i].assign(m+2,1e9);

    krawedzie_gora.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_gora[i].assign(m+2,0);

    krawedzie_dol.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_dol[i].assign(m+2,0);

    krawedzie_lewo.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_lewo[i].assign(m+2,0);

    krawedzie_prawo.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        krawedzie_prawo[i].assign(m+2,0);

    czy_w_MST_poziome.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        czy_w_MST_poziome[i].assign(m+1,false);

    czy_w_MST_pionowe.assign(n+1,{});
    for (int i = 1; i <= n; ++i)
        czy_w_MST_pionowe[i].assign(m+2,false);

    visited.assign(n+2,{});
    for (int i = 1; i <= n+1; ++i)
        visited[i].assign(m+2,false);

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            cin >> wczytany_znak;
            if (wczytany_znak == 'T')
            {
                krawedzie_dol[i][j] = 1;
                krawedzie_gora[i+1][j] = 1;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> wczytany_znak;
            if (wczytany_znak == 'T')
            {
                krawedzie_prawo[i][j] = 1;
                krawedzie_lewo[i][j+1] = 1;
            }
        }
    }

    for (int j = 1; j <= m+1; ++j)
    {
        dp[1][j] = 0;
        Q.push_back({1,j,BRAK,0});
    }
    for (int j = 1; j <= m+1; ++j)
    {
        dp[n+1][j] = 0;
        Q.push_back({n+1,j,BRAK,0});
    }
    for (int i = 2; i <= n; ++i)
    {
        dp[i][1] = 0;
        Q.push_back({i,1,BRAK,0});
    }
    for (int i = 2; i <= n; ++i)
    {
         dp[i][m+1] = 0;
         Q.push_back({i,m+1,BRAK,0});
    }

    while(!Q.empty())
    {
        Pole spr = Q.front();
        Q.pop_front();
        if (spr.val > dp[spr.y][spr.x] or visited[spr.y][spr.x] == true)
            continue;
        visited[spr.y][spr.x] = true;
        if (spr.kier != BRAK)
        {
            if (spr.kier == LEWO)
                czy_w_MST_poziome[spr.y][spr.x-1] = true;
            else if (spr.kier == PRAWO)
                czy_w_MST_poziome[spr.y][spr.x] = true;
            if (spr.kier == GORA)
                czy_w_MST_pionowe[spr.y-1][spr.x] = true;
            else if (spr.kier == DOL)
                czy_w_MST_pionowe[spr.y][spr.x] = true;
        }
        if (spr.y - 1 >= 1)
        {
            if (krawedzie_gora[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y-1][spr.x])
                {
                    dp[spr.y-1][spr.x] = 0;
                    Q.push_front({spr.y-1, spr.x,DOL, 0});
                }
            }
            else
            {
                if (1 < dp[spr.y-1][spr.x])
                {
                    dp[spr.y-1][spr.x] = 1;
                    Q.push_back({spr.y-1, spr.x, DOL,1});
                }
            }
        }
        if (spr.y + 1 <= n+1)
        {
            if (krawedzie_dol[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y+1][spr.x])
                {
                    dp[spr.y+1][spr.x] = 0;
                    Q.push_front({spr.y+1, spr.x, GORA,0});
                }
            }
            else
            {
                if (1 < dp[spr.y+1][spr.x])
                {
                    dp[spr.y+1][spr.x] = 1;
                    Q.push_back({spr.y+1, spr.x, GORA,1});
                }
            }
        }
        if (spr.x - 1 >= 1)
        {
            if (krawedzie_lewo[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y][spr.x-1])
                {
                    dp[spr.y][spr.x-1] = 0;
                    Q.push_front({spr.y, spr.x-1, PRAWO,0});
                }
            }
            else
            {
                if (1 < dp[spr.y][spr.x-1])
                {
                    dp[spr.y][spr.x-1] = 1;
                    Q.push_back({spr.y, spr.x-1, PRAWO,1});
                }
            }
        }
        if (spr.x + 1 <= m+1)
        {
            if (krawedzie_prawo[spr.y][spr.x] == 0)
            {
                if (0 < dp[spr.y][spr.x+1])
                {
                    dp[spr.y][spr.x+1] = 0;
                    Q.push_front({spr.y, spr.x+1, LEWO,0});
                }
            }
            else
            {
                if (1 < dp[spr.y][spr.x+1])
                {
                    dp[spr.y][spr.x+1] = 1;
                    Q.push_back({spr.y, spr.x+1, LEWO,1});
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (czy_w_MST_pionowe[i][j] == true)
            {
                if (krawedzie_dol[i][j] == 0)
                    wyn_cis++;
                else
                    wyn_inne++;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (czy_w_MST_poziome[i][j] == true)
            {
                if (krawedzie_prawo[i][j] == 0)
                    wyn_cis++;
                else
                    wyn_inne++;
            }
        }
    }
    cout << wyn_cis+wyn_inne << ' ' << wyn_cis << '\n';

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 2; j <= m; ++j)
        {
            if (czy_w_MST_pionowe[i][j] == true)
                cout << 'Z';
            else
                cout << '.';
        }
        cout << '\n';
    }
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (czy_w_MST_poziome[i][j] == true)
                cout << 'Z';
            else
                cout << '.';
        }
        cout << '\n';
    }

    return 0;
}

Dzięki za pomoc!

Podobne pytania

0 głosów
1 odpowiedź 593 wizyt
Zadanie Midas finał XXIV OI
pytanie zadane 7 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
0 odpowiedzi 283 wizyt
Zadanie Narciarze OI
pytanie zadane 22 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 158 wizyt
Zadanie Cło 1 etap XV OI
pytanie zadane 20 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,634 zapytań

141,505 odpowiedzi

319,883 komentarzy

62,015 pasjonatów

Kategorie pytań
Programowanie
Sprzęt komputerowy
Systemy operacyjne, programy
Sieci komputerowe
Hostingi, domeny, usługi
Urządzenia mobilne
Bezpieczeństwo, hacking
Rozwój zawodowy, nauka, praca
Egzaminy zawodowe
Matematyka, fizyka, logika
Grafika i multimedia
Ogłoszenia, zlecenia
Nasze projekty
Nasze poradniki
Sprawy forum
Offtop
Programowanie
C i C++ HTML i CSS JavaScript PHP SQL, bazy danych C# Java SPOJ Python Ruby Assembler Visual Basic Android, Swift, Symbian OpenGL, Unity Inne języki Algorytmy Systemy CMS Mikrokontrolery

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

O działaniu forum

Pasja informatyki w internecie

Polecane miejsca w sieci

Snow Theme by Q2A Market
Powered by Question2Answer
...