oj.uz

Submission #864390

# Submission time Handle Problem Language Result Execution time Memory
864390 2023-10-22T16:53:24 Z Ariadna Pohlepko (COCI16_pohlepko) C++14
80 / 80
 130 ms 20052 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector < vector < char > > grid;

void bfs() {
    queue < pair < pair < int, int >, int > > q;
    vector < vector < int > > visited(n, vector < int >(m, 0));
    q.push(make_pair(make_pair(0, 0), 0));
    vector < char > min_char(n + m - 1, 'z');
    min_char[0] = grid[0][0];
    visited[0][0] = 1;
    while (!q.empty()) {
        int i = q.front().first.first;
        int j = q.front().first.second;
        int d = q.front().second;
        q.pop();
        if (grid[i][j] != min_char[d]) continue;
        if (i < n - 1) {
            if (!visited[i + 1][j]) {
                q.push(make_pair(make_pair(i + 1, j), d + 1));
                min_char[d + 1] = min(min_char[d + 1], grid[i + 1][j]);
                visited[i + 1][j] = 1;
            }
            
        }
        if (j < m - 1) {
            if (!visited[i][j + 1]) {
                q.push(make_pair(make_pair(i, j + 1), d + 1));
                min_char[d + 1] = min(min_char[d + 1], grid[i][j + 1]);
                visited[i][j + 1] = 1;
            }
            
        }
    }
    for (int i = 0; i < n + m - 1; ++i) {
        cout << min_char[i];
    }
    cout << '\n';
}

int main()
{
    cin >> n >> m;
    grid = vector < vector < char > >(n, vector < char >(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    bfs();
    
    return 0;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 10 ms 1628 KB Output is correct
7 Correct 57 ms 6896 KB Output is correct
8 Correct 129 ms 20052 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 4 ms 860 KB Output is correct
12 Correct 13 ms 2080 KB Output is correct
13 Correct 7 ms 1372 KB Output is correct
14 Correct 130 ms 20020 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 58 ms 8020 KB Output is correct