제출 #699690

#제출 시각아이디문제언어결과실행 시간메모리
699690TigerpantsTracks in the Snow (BOI13_tracks)C++17
100 / 100
1165 ms255184 KiB
#include <iostream> #include <vector> #include <map> #include <set> #include <algorithm> #include <numeric> #include <unordered_map> #include <random> #include <string> #include <deque> #include <queue> #include <unordered_set> #include <functional> #include <stack> using namespace std; typedef long long int ll; typedef long double ld; typedef vector<ll> vll; typedef vector<ld> vld; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vll> vvll; typedef vector<vld> vvld; typedef vector<vvll> vvvll; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; typedef vector<pll> vpll; typedef stack<pll> stpll; typedef vector<stpll> vstpll; typedef vector<pld> vpld; typedef set<ll> sll; typedef set<pll> spll; typedef map<pll, ll> mpll_ll; typedef map<ll, pll> mll_pll; typedef string str; typedef vector<str> vstr; typedef vector<char> vc; typedef vector<vc> vvc; #define rep(x, a, b) for (ll x = a; x < b; x++) #define rev_rep(x, a, b) for (ll x = a; x >= b; x--) #define itr_rep(type_, x, b) for (type_::iterator x = b.begin(); x != b.end(); x++) #define mp(a, b) make_pair(a, b) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define sz(a) a.size() #define resz(a, b) a.resize(b) #define sort_all(a) sort(all(a)) #define pb(a) push_back(a) #define fill_sz(a, b) fill_n(a.begin(), sz(a), b) const ll INF = 1000000000; ll H, W; vvb fox; vvb rab; vvc board; ll N = 1; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> H >> W; resz(fox, H); resz(rab, H); resz(board, H); rep(i, 0, H) { resz(fox[i], W); resz(rab[i], W); resz(board[i], W); fill_sz(fox[i], false); fill_sz(rab[i], false); } rep(i, 0, H) { rep(j, 0, W) { cin >> board[i][j]; fox[i][j] = (board[i][j] == 'F'); rab[i][j] = (board[i][j] == 'R'); } } vpll cur_bfs; vpll nxt_bfs; vvll dst; resz(dst, H); rep(i, 0, H) {resz(dst[i], W); fill_sz(dst[i], INF);} cur_bfs.push_back(mp(0, 0)); dst[0][0] = 0; ll dx[4] = {0, 1, 0, -1}; ll dy[4] = {1, 0, -1, 0}; ll ptr = 0; while (not cur_bfs.empty()) { pll nx = cur_bfs.back(); cur_bfs.pop_back(); if (dst[nx.first][nx.second] != ptr) continue; N = ptr; rep(i, 0, 4) { pll nw = mp(nx.first + dx[i], nx.second + dy[i]); if ((0 <= nw.first) and (nw.first < H) and (0 <= nw.second) and (nw.second < W)) { if (board[nx.first][nx.second] == board[nw.first][nw.second]) { if (dst[nx.first][nx.second] < dst[nw.first][nw.second]) { dst[nw.first][nw.second] = dst[nx.first][nx.second]; cur_bfs.push_back(nw); } } else if (board[nw.first][nw.second] != '.') { if (dst[nx.first][nx.second] + 1 < dst[nw.first][nw.second]) { dst[nw.first][nw.second] = dst[nx.first][nx.second] + 1; nxt_bfs.push_back(nw); } } } } if (cur_bfs.empty()) { swap(nxt_bfs, cur_bfs); ptr++; } } cout << N + 1 << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...