Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <map>
- #define F first
- #define S second
- #define pb push_back
- #include <vector>
- #include <queue>
- #pragma comment(linker, "/stack:200000000")
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- using namespace std;
- int n, m, k, t;
- const int N = 1e6+2;
- char arr[1001][1001];
- vector<vector<int>> g(1000001);
- bool v[N];
- int wave[N];
- queue<int> q;
- void bfs(){
- int st;
- st = (n-2)*(m-2);
- q.push(st);
- v[st] = true;
- wave[st] = 0;
- while(!q.empty()){
- st = q.front();
- q.pop();
- for(auto x:g[st]){
- if(!v[x]){
- v[x] = true;
- wave[x] = wave[st]+1;
- q.push(x);
- //cout << x << " " << wave[x] << endl;
- }
- }
- }
- cout << wave[1] << endl;
- if(wave[1] < wave[t]) cout << "Yes\n";
- else cout << "No\n";
- }
- int main()
- {
- cin >> n >> m;
- for(int i = 0; i < n; ++i){
- for(int j = 0; j < m; ++j){
- cin >> arr[i][j];
- }
- }
- for(int i = 1; i < n - 1; ++i){
- for(int j = 1; j < m - 1; ++j){
- k++;
- if(arr[i][j]=='#')continue;
- if(arr[i][j]=='T') t = k, arr[i][j] = '.';
- if(i > 1 && arr[i-1][j]!='#')g[k].pb(k - m + 2);
- if(i < n - 1 && arr[i+1][j]!='#')g[k].pb(k + m - 2);
- if(j > 1 && arr[i][j-1]!='#')g[k].pb(k - 1);
- if(j < m - 1 && arr[i][j+1]!='#')g[k].pb(k + 1);
- }
- }
- //cout << t << endl;
- /*for(int i = 1; i <= (n-2)*(m-2); ++i){
- for(auto x:g[i])cout << x << " ";
- cout << endl;
- }*/
- bfs();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement