Submission #166837

#TimeUsernameProblemLanguageResultExecution timeMemory
166837sansPohlepko (COCI16_pohlepko)C++14
40 / 80
1076 ms51884 KiB
#include <iostream> #include <numeric> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <string> #include <set> #include <map> using namespace std; #define sp ' ' #define st first #define nd second #define pb push_back #define mp make_pair #define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy) #define prn(XX) cout << XX << endl #define prs(XX) cout << XX << " " typedef long long int ll; typedef unsigned long long int ull; typedef vector<ll> vll; typedef vector<vector<ll>> vvll; typedef pair<ll, ll> pll; typedef vector<pll> vpll; const int MOD = 1e9 + 7; const int INF = 2e9 + 13; const int mINF = -2e9 - 13; const double PI = 3.14159265358979; const double EPS = 1e-9; int N, M; vector<vector<char>> grid; map<pair<int, int>, bool> visited; int main(int argc, char **argv){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; grid.resize(N, vector<char>(M)); for(int i = 0; i < N; ++i) for(int j = 0; j < M; ++j) cin >> grid[i][j]; queue<pair<string, pair<int, int>>> q; string s; s += grid[0][0]; q.push(mp(s, mp(0, 0))); set<string> Set; while(!q.empty()){ pair<string, pair<int, int>> t = q.front(); q.pop(); int x = t.nd.st, y = t.nd.nd; if(x == N-1 and y == M-1){ Set.insert(t.st); continue; } if(x < N-1 and y < M-1){ if(grid[x][y+1] < grid[x+1][y]){ if(!visited[mp(x, y+1)]){ visited[mp(x, y+1)] = true; q.push(mp(t.st + grid[x][y+1], mp(x, y+1))); } } else if(grid[x][y+1] > grid[x+1][y]){ if(!visited[mp(x+1, y)]){ visited[mp(x+1, y)] = true; q.push(mp(t.st + grid[x+1][y], mp(x+1, y))); } } else{ if(!visited[mp(x+1, y)]){ visited[mp(x+1, y)] = true; q.push(mp(t.st + grid[x+1][y], mp(x+1, y))); } if(!visited[mp(x, y+1)]){ visited[mp(x, y+1)] = true; q.push(mp(t.st + grid[x][y+1], mp(x, y+1))); } } } else if(x >= N-1 and y < M-1){ if(!visited[mp(x, y+1)]){ visited[mp(x, y+1)] = true; q.push(mp(t.st + grid[x][y+1], mp(x, y+1))); } } else if(x < N-1 and y >= M-1){ if(!visited[mp(x+1, y)]){ visited[mp(x+1, y)] = true; q.push(mp(t.st + grid[x+1][y], mp(x+1, y))); } } } cout << *(Set.begin()) << endl; return 0; } //cikisir
#Verdict Execution timeMemoryGrader output
Fetching results...