# hihoCoder 1519-逃离迷宫II

hihoCoder 1519-逃离迷宫II

### 输出

```5 5
S.#.T
.....
.....
.....
.....```

`2`

```#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;

const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
int ans = INT_MAX;

vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<char>> visited(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ {-1,0},{1,0},{0,-1},{0,1} }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向

bool ok(int x, int y) {
if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
return false;
}

void dfs(int sx,int sy, int step) {
for (int i = 0; i < 4; ++i) {
int newx = sx + dirs[i][0], newy = sy + dirs[i][1];
if (ok(newx, newy) && visited[newx][newy] == '0') {
visited[newx][newy] = '1';
bool done = false;
while (ok(newx, newy)) {
visited[newx][newy] = '1';
if (newx == endx&&newy == endy) {
done = true;
break;
}
newx = newx + dirs[i][0], newy = newy + dirs[i][1];
}
if (done) {
ans = min(ans, step);
}
else {
dfs(newx + opdirs[i][0], newy + opdirs[i][1], step + 1);  // 往回走一步再递归
}

while (!(newx == sx&&newy == sy)) {
if (ok(newx, newy))visited[newx][newy] = '0'; // 复位
newx = newx + opdirs[i][0], newy = newy + opdirs[i][1];
}
}
}

}

int main() {
//freopen("input.txt", "r", stdin);

scanf("%d %d", &n, &m);
char c;

for (int i = 0; i < n; ++i) {
scanf("%c", &c);
for (int j = 0; j < m; ++j) {
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
else if (maze[i][j] == 'T') {
endx = i;
endy = j;
}
}
}
visited[startx][starty] = '1';
dfs(startx, starty, 0);
if (ans == INT_MAX)printf("-1\n");
else printf("%d\n", ans);
return 0;
}
```

```#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
#include<queue>
using namespace std;

const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;

typedef struct P {
int x, y, step;
P(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {};
};

vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
set<int> points;

bool ok(int x, int y) {
if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
return false;
}

int id(int x, int y) {
return x*n + y;
}

int bfs() {
queue<P> q;
P p(startx, starty, 0);
q.push(p);
while (!q.empty()) {
p = q.front();
q.pop();
points.insert(id(p.x, p.y));

for (int i = 0; i < dirs.size(); ++i) {
int newx = p.x + dirs[i][0], newy = p.y + dirs[i][1];
while (ok(newx, newy)) {
if (newx == endx&&newy == endy) {
return p.step;
}
newx = newx + dirs[i][0], newy = newy + dirs[i][1];
}
int cornorx = newx + opdirs[i][0], cornory = newy + opdirs[i][1]; // 往回走一步
if (points.find(id(cornorx, cornory)) == points.end()) {
P tmp(cornorx, cornory, p.step + 1);
q.push(tmp);
}
}
}
return -1;
}

int main() {
//freopen("input.txt", "r", stdin);

scanf("%d %d", &n, &m);
char c;

for (int i = 0; i < n; ++i) {
scanf("%c", &c);
for (int j = 0; j < m; ++j) {
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
else if (maze[i][j] == 'T') {
endx = i;
endy = j;
}
}
}
printf("%d\n", bfs());
return 0;
}
```