Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <fstream>
- //#include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1005;
- const int INF = 1e9;
- const int di[] = {-1, 1, 0, 0};
- const int dj[] = {0, 0, -1, 1};
- int n, m;
- char mat[maxn][maxn];
- int dist[maxn][maxn];
- void paralel_bfs() {
- queue<int> q;
- vector<vector<bool>> v(n, vector<bool>(m, false));
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- dist[i][j] = -1;
- if(mat[i][j] == 'G') {
- q.push(i);
- q.push(j);
- q.push(0);
- v[i][j] = true;
- }
- }
- }
- while(!q.empty()) {
- int ci = q.front(); q.pop();
- int cj = q.front(); q.pop();
- int cekor = q.front(); q.pop();
- if(mat[ci][cj] != 'G') {
- dist[ci][cj] = cekor;
- }
- // cout << ci << " " << cj << endl;
- for(int i = 0; i < 4; i++) {
- int ti = ci + di[i];
- int tj = cj + dj[i];
- if(ti >= 0 and ti < n and tj >= 0 and tj < m and dist[ti][tj] == -1 and mat[ti][tj] == '.' and !v[ti][tj]) {
- q.push(ti);
- q.push(tj);
- q.push(cekor + 1);
- v[ti][tj] = true;
- }
- }
- }
- }
- struct node {
- int ci, cj, d;
- node () {}
- node(int _ci, int _cj, int _d) {
- ci = _ci;
- cj = _cj;
- d = _d;
- }
- bool operator < (const node & tmp) const {
- return d < tmp.d;
- }
- };
- bool visited[maxn][maxn];
- void dijkstra(int si, int sj, int ei, int ej) {
- }
- int main() {
- ios_base::sync_with_stdio(false);
- // ifstream cin("in.txt");
- cin >> n >> m;
- int si, sj, ei, ej;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- cin >> mat[i][j];
- if(mat[i][j] == 'R') {
- si = i;
- sj = j;
- }
- if(mat[i][j] == 'Z') {
- ei = i;
- ej = j;
- }
- }
- }
- mat[ei][ej] = '.';
- mat[si][sj] = '.';
- // cout << "DA" << endl;
- paralel_bfs();
- // cout << "DA" << endl;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- visited[i][j] = false;
- }
- }
- priority_queue<node> pq;
- pq.push(node(si, sj, dist[si][sj]));
- int min_value = INF;
- while(!pq.empty()) {
- node c = pq.top();
- pq.pop();
- min_value = min(min_value, c.d);
- if(ei == c.ci and ej == c.cj) {
- cout << min_value << endl;
- break;
- }
- // cout << c.ci << " " << c.cj << endl;
- for(int i = 0; i < 4; i++) {
- int ti = c.ci + di[i];
- int tj = c.cj + dj[i];
- if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] == '.') {
- pq.push(node(ti, tj, dist[ti][tj]));
- visited[ti][tj] = true;
- }
- }
- }
- return 0;
- }
- /*
- .R234....
- ..1.3.1..
- ..G121G1.
- ....221..
- G...122..
- ....G12..
- ...**.3..
- ...Z..4..
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement