Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- signed main() {
- ios_base::sync_with_stdio(0); cin.tie(0);
- ll h, w; cin >> h >> w;
- string s[h];
- for (auto &u : s) cin >> u;
- ll cost[h][w];
- for (ll i = 0; i < h; i++) for (ll j = 0; j < w; j++) cost[i][j] = 1e18;
- auto isValid = [&](ll i, ll j) {
- return (i >= 0 and i < h and j >= 0 and j < w and s[i][j] == '.');
- };
- char ans[h][w];
- queue<pair<ll, ll>> q;
- bool visited[h][w];
- memset(visited, false, sizeof(visited));
- for (ll i = 0; i < h; i++) {
- for (ll j = 0; j < w; j++) {
- if (s[i][j] != '.') ans[i][j] = s[i][j];
- if (s[i][j] != 'E') continue;
- q.push({i, j});
- cost[i][j] = 0;
- visited[i][j] = true;
- }
- }
- while (!q.empty()) {
- auto [i, j] = q.front();
- q.pop();
- pair<ll, ll> d[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
- for (auto &[dx, dy] : d) {
- ll x = i+dx, y = j+dy;
- if (isValid(x, y) and !visited[x][y] and cost[x][y] > cost[i][j]+1) {
- cost[x][y] = cost[i][j]+1;
- if (i == x) {
- if (j < y) ans[x][y] = '<';
- else ans[x][y] = '>';
- }
- else {
- if (i < x) ans[x][y] = '^';
- else ans[x][y] = 'v';
- }
- q.push({x, y});
- visited[x][y] = true;
- }
- }
- }
- for (auto &u : ans) {
- for (auto &v : u) cout << v;
- cout << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
