Submission #864352

#	Time	Username	Problem	Language	Result	Execution time	Memory
864352		Ariadna	Pohlepko (COCI16_pohlepko)	C++14	30 / 80	1078 ms	65536 KiB

pohlepko

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector < vector < char > > grid;
vector < vector < int > > adj;
string s = "", ans = "";

void dfs(int u) {
    int i = u / m, j = u % m;
    s += grid[i][j];
    if (u == n * m - 1) {
        if (ans == "") ans = s;
        else ans = min(ans, s);
    } else {
        if (i == n - 1) dfs(u + 1);
        else if (j == m - 1) dfs(u + 1);
        else {
            if (grid[i + 1][j] <= grid[i][j + 1]) dfs(u + m);
            if (grid[i + 1][j] >= grid[i][j + 1]) dfs(u + 1);
        }
        
    }
    s.pop_back();
}

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];
        }
    }
    adj = vector < vector < int > >(n * m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i < n - 1) adj[i * m + j].push_back((i + 1) * m + j);
            if (j < m - 1) adj[i * m + j].push_back(i * m + j + 1);
        }
    }
    dfs(0);
    cout << ans << '\n';
    
    return 0;
}

• Subtask 1: 30 / 80