Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <queue>
- using namespace std;
- struct Pos{
- int i;
- int j;
- };
- bool operator !=(Pos a, Pos b){
- return !(a.i == b.i && a.j == b.j);
- }
- int main(){
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n, m;
- cin>>n>>m;
- vector<Pos > teleport;
- vector<vector<char> > g(n, vector<char>(m));
- vector<vector<int> > d(n, vector<int>(m, 1e7));
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- cin>>g[i][j];
- if(g[i][j] == 'T'){
- teleport.push_back(Pos{i, j});
- }
- }
- }
- int x1, y1, x2, y2;
- cin>>x1>>y1>>x2>>y2;
- x1--;y1--;x2--;y2--;
- queue<Pos> q;
- q.push(Pos{x1, y1});
- d[x1][y1] = 0;
- while(true){
- Pos v = q.front();
- q.pop();
- for(int di = -1; di <= 1; di++){
- for(int dj = -1; dj <= 1; dj++){
- if(di * di + dj * dj == 1){
- int ni = v.i + di;
- int nj = v.j + dj;
- if(ni >= 0 && ni < n && nj >= 0 && nj < m && d[ni][nj] > d[v.i][v.j]){
- q.push(Pos{ni, nj});
- d[ni][nj] = d[v.i][v.j] + 1;
- }
- }
- }
- }
- if(g[v.i][v.j] == 'T'){
- for(auto i : teleport){
- if(d[i.i][i.j] > d[v.i][v.j]){
- q.push(i);
- d[i.i][i.j] = d[v.i][v.j];
- }
- }
- }
- if(d[x2][y2] != 1e7){
- cout<<d[x2][y2];
- return 0;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement