133NSON edited 3 年,2 月前
#include <iostream>
#include <vector>
// #include <queue>
using namespace std;
struct point1
{
int x;
int y;
int n;
bool b;
};
struct myQue
{
point1 ap[500000] = {0};
int fir;
int back;
point1 front()
{
return ap[fir];
}
void push(int x, int y, int n, bool b)
{
point1 tmp{x, y, n, b};
ap[back++] = tmp;
if (back == 500000) {
back = 0;
}
}
bool empty()
{
return back == fir;
}
void pop()
{
fir++;
if (fir == 500000) {
fir = 0;
}
}
};
int bfs(vector<vector<char>>, int, int);
int main()
{
int n, m, sx, sy;
while (cin >> n >> m)
{
vector<vector<char>> a;
a.resize(n);
for (int i{}; i < n; i++) {
for (int j{}; j < m; j++) {
char tmp;
cin >> tmp;
a[i].push_back(tmp);
if (tmp == 'S') {
sx = i;
sy = j;
}
}
}
int can = bfs(a, sx, sy);
if (can) {
cout << can;
} else {
cout << "impossible";
}
cout << endl;
}
return 0;
}
// int bfs(vector<vector<char>> a, int x, int y)
// {
// queue<point1> q;
// q.push({x, y, 0, 0});
// for ( ; !(q.empty()); a[q.front().x][q.front().y] = '#', q.pop()) {
// if (q.front().b) {
// q.push({q.front().x, q.front().y, q.front().n, false});
// continue;
// }
// if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == '.') {
// q.push({q.front().x + 1, q.front().y, q.front().n + 1, false});
// } else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'X') {
// q.push({q.front().x + 1, q.front().y, q.front().n + 2, true});
// } else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'T') {
// return q.front().n + 1;
// }
// if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == '.') {
// q.push({q.front().x - 1, q.front().y, q.front().n + 1, false});
// } else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'X') {
// q.push({q.front().x - 1, q.front().y, q.front().n + 2, true});
// } else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'T') {
// return q.front().n + 1;
// }
// if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == '.') {
// q.push({q.front().x, q.front().y + 1, q.front().n + 1, false});
// } else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'X') {
// q.push({q.front().x, q.front().y + 1, q.front().n + 2, true});
// } else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'T') {
// return q.front().n + 1;
// }
// if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == '.') {
// q.push({q.front().x, q.front().y - 1, q.front().n + 1, false});
// } else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'X') {
// q.push({q.front().x, q.front().y - 1, q.front().n + 2, true});
// } else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'T') {
// return q.front().n + 1;
// }
// }
// return 0;
// }
int bfs(vector<vector<char>> a, int x, int y)
{
myQue q;
q.fir = 0;
q.back = 0;
q.push(x, y, 0, 0);
for ( ; !(q.empty()); a[q.front().x][q.front().y] = '#', q.pop()) {
if (q.front().b) {
q.push(q.front().x, q.front().y, q.front().n, false);
continue;
}
if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == '.') {
q.push(q.front().x + 1, q.front().y, q.front().n + 1, false);
} else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'X') {
q.push(q.front().x + 1, q.front().y, q.front().n + 2, true);
} else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'T') {
return q.front().n + 1;
}
if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == '.') {
q.push(q.front().x - 1, q.front().y, q.front().n + 1, false);
} else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'X') {
q.push(q.front().x - 1, q.front().y, q.front().n + 2, true);
} else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'T') {
return q.front().n + 1;
}
if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == '.') {
q.push(q.front().x, q.front().y + 1, q.front().n + 1, false);
} else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'X') {
q.push(q.front().x, q.front().y + 1, q.front().n + 2, true);
} else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'T') {
return q.front().n + 1;
}
if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == '.') {
q.push(q.front().x, q.front().y - 1, q.front().n + 1, false);
} else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'X') {
q.push(q.front().x, q.front().y - 1, q.front().n + 2, true);
} else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'T') {
return q.front().n + 1;
}
}
return 0;
}