Riešenie hrubou silou

Úlohu vieme naivne riešiť pomocou hrubej sily. Pre každú súradnicu, kde mohol had začať, môžeme odsimulovať pohyb hada nasledovným spôsobom. Každým krokom si vypočítame zmenu súradníc:

1. H: y+=1

2. D: y-=1

3. P: x+=1

4. L: x-=1

Skontrolujeme či sme nevyšli z mriežky, teda skontrolujeme či platia nerovnosti: 1. $0 \leq x \leq m$ 2. $0 \leq y \leq n$

Ešte nám zostáva skontrolovať či had nerazil sám do seba. To vieme napríklad takto.

Zakaždým si uložíme pár súradníc do listu a skontrolujeme či sa tam už nenachádzali predtým. Ak sa v liste už súradnice nachádzajú, tak had narazil sám do seba.

Optimálne riešenie

Základným pozorovaním v úlohe je, že had sa pohybuje iba v obdĺžniku s rozmermi $a,b$. V úlohe sa teda pýtame koľkými spôsobmi vieme umiestniť tento obdĺžnik do mriežky zo zadania. Zároveň platí, že ak had narazí sám do seba nebude to závisieť od pozície obdĺžnika a narazí zakaždým. Pri kontrole narazení hada do samého seba je však potrebné použiť dátovú štruktúru set (unordered). Takto budeme môcť vkladať súradnice a kontrolovať ich výskyt v časovej zložitosti O(1).¹

Rozmery tohto obdĺžnika získame tak, že si budeme pamätať minimum a maximum z týchto hodnôt a neskôr ich od seba odčítame.

Počet možností ako vieme umiestniť tento obdĺžnik do mriežky zo zadania vieme vypočítať ako $(m-a) \times (n-b)$ kde:

$a = max_x - min_x$

$b = max_y - min_y$

Umiestnenie obdĺžnika si vieme predstaviť ako umiestnenie ľavého horného bodu obdĺžnika, tak aby pravý dolný bod nevyčnieval z mriežky.

Časová a pamäťová zložitosť

Takéto riešenie bude mať časovú zložitosť $O(t)$ a pamäťovú zložitosť $O(t)$

Všetky set-ové operácie, ktoré vykonávame $t$-krát budú v O(1) čase. Kvôli kontrole kolízie hada, si budeme potrebovať pamätať všetkých $t$ súradníc.

Plné body môžete získať aj keď využijete ordered set.

N, M = map(int, input().split())
S = input()

cur = (0, 0)
vis = set()
maxx, minx, maxy, miny = 0, 0, 0, 0

for ch in S:
    if ch == "D":
        cur = (cur[0]-1, cur[1])
    if ch == "H":
        cur = (cur[0]+1, cur[1])
    if ch == "P":
        cur = (cur[0], cur[1]+1)
    if ch == "L":
        cur = (cur[0], cur[1]-1)

    maxx = max(maxx, cur[0])
    minx = min(minx, cur[0])
    maxy = max(maxy, cur[1])
    miny = min(miny, cur[1])

    if cur in vis:
        print(0)
        exit()

    vis.add(cur)

width = maxx-minx
height = maxy-miny

if (M-width) <= 0 or (N-height) <= 0:
    print(0)
    exit()

print((M-width)*(N-height))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    ll m, n;
    cin >>m>>n;
    string s;
    cin >>s;

    set<pair<int,int>> visited;
    ll x = 0; ll y = 0;
    bool narazil = false;

    ll max_x = 0; ll min_x = 0; ll max_y = 0; ll min_y = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'H'){
            y++;
        }else if(s[i] == 'D'){
            y--;
        }else if (s[i] == 'P'){
            x++;
        }else{
            x--;
        }

        max_x = max(x, max_x);
        min_x = min(x, min_x);
        max_y = max(y, max_y);
        min_y = min(y, min_y);

        if(visited.count({x,y}) > 0) {
            narazil = true;
        }
        visited.insert({x,y});
    }

    if (narazil or max_x - min_x > m or max_y - min_y > n){
        cout << "0\n";
    }else{
        cout << (m - (max_x-min_x)) * (n - (max_y-min_y))<< '\n'; 
    }

}