Advertisement
Guest User

Untitled

a guest
Aug 18th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.74 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <map>
  4. #define F first
  5. #define S second
  6. #define pb push_back
  7. #include <vector>
  8. #include <queue>
  9. #pragma comment(linker, "/stack:200000000")
  10. #pragma GCC optimize("Ofast")
  11. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  12.  
  13.  
  14. using namespace std;
  15.  
  16. int n, m, k, t;
  17.  
  18. const int N = 1e6+2;
  19.  
  20. char arr[1001][1001];
  21. vector<vector<int>> g(1000001);
  22. bool v[N];
  23. int wave[N];
  24. queue<int> q;
  25.  
  26. void bfs(){
  27.     int st;
  28.     st = (n-2)*(m-2);
  29.     q.push(st);
  30.     v[st] = true;
  31.     wave[st] = 0;
  32.     while(!q.empty()){
  33.         st = q.front();
  34.         q.pop();
  35.         for(auto x:g[st]){
  36.             if(!v[x]){
  37.                 v[x] = true;
  38.                 wave[x] = wave[st]+1;
  39.                 q.push(x);
  40.                 //cout << x << " " << wave[x] << endl;
  41.             }
  42.         }
  43.     }
  44.     cout << wave[1] << endl;
  45.     if(wave[1] < wave[t]) cout << "Yes\n";
  46.     else cout << "No\n";
  47. }
  48.  
  49. int main()
  50. {
  51.     cin >> n >> m;
  52.     for(int i = 0; i < n; ++i){
  53.         for(int j = 0; j < m; ++j){
  54.             cin >> arr[i][j];
  55.         }
  56.     }
  57.     for(int i = 1; i < n - 1; ++i){
  58.         for(int j = 1; j < m - 1; ++j){
  59.             k++;
  60.             if(arr[i][j]=='#')continue;
  61.             if(arr[i][j]=='T') t = k, arr[i][j] = '.';
  62.             if(i > 1 && arr[i-1][j]!='#')g[k].pb(k - m + 2);
  63.             if(i < n - 1 && arr[i+1][j]!='#')g[k].pb(k + m - 2);
  64.             if(j > 1 && arr[i][j-1]!='#')g[k].pb(k - 1);
  65.             if(j < m - 1 && arr[i][j+1]!='#')g[k].pb(k + 1);
  66.         }
  67.     }
  68.     //cout << t << endl;
  69.     /*for(int i = 1; i <= (n-2)*(m-2); ++i){
  70.         for(auto x:g[i])cout << x << " ";
  71.         cout << endl;
  72.     }*/
  73.     bfs();
  74.     return 0;
  75.  
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement