Submission #1236131

#TimeUsernameProblemLanguageResultExecution timeMemory
1236131ghassanhasanPatkice II (COCI21_patkice2)C++20
0 / 110
7 ms16708 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e3 + 5, di[] = {0, 0, 1, -1}, dj[] = {-1, 1, 0, 0};
const string D = "RLUD", C = "<>v^";
vector grid(N, string());
vector vis(N, vector<bool>(N));
vector par(N, vector<int>(N, -1));
int n, m, si, sj, ei, ej;
bool valid(int i, int j)
{
    return i >= 0 && j >= 0 && i < n && j < m && !vis[i][j];
}
void dfs(int i, int j, vector<pair<int, int>> &ret)
{
    ret.emplace_back(i, j);
    vis[i][j] = 1;
    for (int k = 0; k < 4; k++)
    {
        int ni = i + di[k], nj = j + dj[k];
        if (valid(ni, nj))
        {
            if (grid[i][j] == C[k])
                dfs(ni, nj, ret);
            par[ni][nj] = k;
        }
    }
}
void bfs()
{
    vector<pair<int, int>> q;
    vis[si][sj] = 1;
    for (int k = 0; k < 4; k++)
    {
        int ni = si + di[k], nj = sj + dj[k];
        if (valid(si + di[k], sj + dj[k]))
        {
            q.emplace_back(ni, nj);
            par[ni][nj] = k;
            vis[ni][nj] = 1;
        }
    }
    vector<pair<int, int>> cur;
    for (int st = 0; st < int(q.size()); st++)
    {
        auto [i, j] = q[st];
        dfs(i, j, cur);
        for (auto [a, b] : cur)
        {
            for (int k = 0; k < 4; k++)
            {
                int ni = a + di[k], nj = b + dj[k];
                if (valid(ni, nj) && grid[a][b] != C[k])
                {
                    vis[ni][nj] = 1;
                    par[ni][nj] = k;
                    q.emplace_back(ni, nj);
                }
            }
        }
        if (vis[ei][ej])
            return;
        cur.clear();
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> grid[i];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (grid[i][j] == 'o')
                si = i, sj = j;
            else if (grid[i][j] == 'x')
                ei = i, ej = j;
        }
    }
    bfs();
    int ans = 0;
    while (par[ei][ej] != -1)
    {
        int k = par[ei][ej];
        int i = ei - di[k], j = ej - dj[k];
        if (grid[i][j] != C[k])
            ans++;
        grid[i][j] = C[k];
        ei = i;
        ej = j;
    }
    cout << ans - 1 << '\n';
    grid[si][sj] = 'o';
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << grid[i][j];
        }
        cout << '\n';
    }
    cout.flush();
    system("pause");
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:108:11: warning: ignoring return value of 'int system(const char*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     system("pause");
      |     ~~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...