oj.uz

답안 #1053792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1053792 2024-08-11T17:37:19 Z SamAnd Bikeparking (EGOI24_bikeparking) C++17
0 / 100
 2 ms 1372 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 403;
const int xx[9] = {0, 1, 0, -1, 1, -1, 1, -1, 0};
const int yy[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};

int n, m;
char a[N][N];

int rec(vector<pair<int, int> > s, vector<vector<bool> > cc, vector<vector<bool> > tt)
{
    vector<vector<bool> > c(2 * N, vector<bool>(2 * N, false));
    queue<pair<int, int> > q;
    q.push(m_p(0, 0));
    tt[N + 0][N + 0] = true;
    cc[N + 0][N + 0] = true;
    int ans = 0;
    while (!q.empty())
    {
        int dx = q.front().fi;
        int dy = q.front().se;
        q.pop();

        if (cc[N + dx][N + dy] == false)
        {
            cc[N + dx][N + dy] = true;
            map<string, vector<pair<int, int> > > mp;
            for (int i = 0; i < sz(s); ++i)
            {
                string ss = "";
                for (int j = 0; j < 9; ++j)
                {
                    int x = s[i].fi + dx + xx[j];
                    int y = s[i].se + dy + yy[j];
                    if (a[x][y] == 'X')
                        ss += '.';
                    else
                        ss += a[x][y];
                }
                mp[ss].push_back(s[i]);
            }
            if (sz(mp) > 1)
            {
                ans = N * N;
                for (auto it = mp.begin(); it != mp.end(); ++it)
                {
                    ans = min(ans, rec(it->se, cc, tt));
                }
                return ans;
            }
        }

        {
            int x = s[0].fi + dx;
            int y = s[0].se + dy;
            if (a[x][y] == 'o')
                ++ans;
        }

        for (int i = 0; i < 4; ++i)
        {
            int ndx = dx + xx[i];
            int ndy = dy + yy[i];
            bool z = true;
            if (tt[N + ndx][N + ndy] == false)
            {
                for (int i = 0; i < sz(s); ++i)
                {
                    int x = s[i].fi + ndx;
                    int y = s[i].se + ndy;
                    if (a[x][y] == 'X' || a[x][y] == '#')
                    {
                        z = false;
                        break;
                    }
                }
            }
            if (z)
            {
                if (c[N + ndx][N + ndy] == false)
                {
                    q.push(m_p(ndx, ndy));
                    tt[N + ndx][N + ndy] = true;
                    c[N + ndx][N + ndy] = true;
                }
            }
        }
    }

    return ans;
}

void solv()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> (a[i] + 1);
    }

    vector<pair<int, int> > s;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i][j] == 'S')
            {
                s.push_back(m_p(i, j));
                a[i][j] = '.';
            }
        }
    }

    vector<vector<bool> > gg(2 * N, vector<bool>(2 * N, false));
    cout << rec(s, gg, gg) << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Subtask #1
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -