Submission #864390

#	Time	Username	Problem	Language	Result	Execution time	Memory
864390		Ariadna	Pohlepko (COCI16_pohlepko)	C++14	80 / 80	130 ms	20052 KiB

pohlepko

#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 / 80