Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <queue>
- using namespace std;
- int main()
- {
- // ofstream cout("out.txt");
- int n, m;
- char mat[1000][1000];
- cin >> n >> m;
- queue<int> q;
- for (int i = 0; i < n; i++){
- for (int j = 0; j < m; j++){
- cin >> mat[i][j];
- }
- }
- bool visited[1000][1000];
- for (int i = 0; i < n; i++){
- for (int j = 0; j < m; j++){
- visited[i][j] = false;
- }
- }
- int di[] = {1, -1, 0, 0};
- int dj[] = {0, 0, 1, -1};
- for (int i = 0; i < n; i++){
- for (int j = 0; j < m; j++){
- if (mat[i][j] == 'S'){
- q.push(i);
- q.push(j);
- q.push(0);
- visited[i][j] = true;
- }
- }
- }
- while (!q.empty()){
- int ci, cj, dist;
- ci = q.front();
- q.pop();
- cj = q.front();
- q.pop();
- dist = q.front();
- q.pop();
- if (mat[ci][cj] == 'E'){
- cout << dist << endl;
- return 0;
- }
- for (int i = 0; i < 4; i++){
- int ti = ci + di[i], tj = cj + dj[i];
- if (ti >= n or ti < 0 or tj >= m or tj < 0) continue;
- if (visited[ti][tj] == true) continue;
- if (mat[ti][tj] == '#') continue;
- q.push(ti);
- q.push(tj);
- q.push(dist + 1);
- visited[ti][tj] = true;
- }
- }
- int najgolem_pat = -1;
- for (int i = 0; i < n; i++){
- for (int j = 0; j < m; j++){
- if (mat[i][j] == '#'){
- for (int p = 0; p < n; p++){
- for (int k = 0; k < m; k++){
- visited[p][k] = false;
- }
- }
- q.push(i);
- q.push(j);
- q.push(0);
- visited[i][j] = true;
- int diste = -1, dists = -1;
- while (!q.empty()){
- int ci, cj, dist;
- ci = q.front();
- q.pop();
- cj = q.front();
- q.pop();
- dist = q.front();
- q.pop();
- if (mat[ci][cj] == 'E'){
- diste = dist;
- }
- if (mat[ci][cj] == 'S'){
- dists = dist;
- }
- for (int z = 0; z < 4; z++){
- int ti = ci + di[z], tj = cj + dj[z];
- if (ti >= n or ti < 0 or tj >= m or tj < 0) continue;
- if (visited[ti][tj] == true) continue;
- if (mat[ti][tj] == '#') continue;
- q.push(ti);
- q.push(tj);
- q.push(dist + 1);
- visited[ti][tj] = true;
- }
- }
- // cout << diste << " " << dists << endl;
- if(diste == -1 or dists == -1) continue;
- if (diste + dists > najgolem_pat){
- najgolem_pat = diste + dists;
- }
- }
- }
- }
- cout << najgolem_pat << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement