Submission #1180242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180242		NValchanov	Land of the Rainbow Gold (APIO17_rainbow)	C++20	11 / 100	3095 ms	1114112 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector < vector < bool > > a;
vector < vector < bool > > visited;
int X1, Y1, X2, Y2;

void init(int N, int M, int sr, int sc, int len, char *s) 
{
    n = N;
    m = M;
    a.resize(n + 1);
    visited.resize(n + 1);

    for(int i = 0; i <= n; i++)
    {
        a[i].resize(m + 1, 0);
        visited[i].resize(m + 1, 0);
    }

    int posx = sr;
    int posy = sc;

    a[posx][posy] = true;

    for(int i = 0; i < len; i++)
    {
        if(s[i] == 'N')
            posx--;
        else if(s[i] == 'S')
            posx++;
        else if(s[i] == 'W')
            posy--;
        else
            posy++;

        //cout << posx << " " << posy << endl;
        
        a[posx][posy] = true;
    }

}

bool check(int x, int y)
{
    return X1 <= x && x <= X2 && Y1 <= y && y <= Y2 && !visited[x][y] && !a[x][y];
}

void dfs(int x, int y)
{
    //cout << "Tuka sum : " << x << " - " << y << endl;
    visited[x][y] = true;

    for(int dx = -1; dx <= 1; dx++)
    {
        for(int dy = -1; dy <= 1; dy++)
        {
            if(abs(dx) == abs(dy))
                continue;

            int nbx = x + dx;
            int nby = y + dy;

            if(check(nbx, nby))
                dfs(nbx, nby);
        }
    }
}

int colour(int x1, int y1, int x2, int y2) 
{
    X1 = x1;
    Y1 = y1;
    X2 = x2;
    Y2 = y2;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            visited[i][j] = false;
        }
    }

    int ans = 0;

    for(int i = X1; i <= X2; i++)
    {
        for(int j = Y1; j <= Y2; j++)
        {
            if(check(i, j))
            {
                dfs(i, j);
                ans++;
            }
        }
    }

    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26