簡單來說就做最基本的BFS
be like:

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

int n, m;

char mp[1000][1000];

bool visited[1000][1000];

 

int dx[4] = {0, 1, -1, 0};

int dy[4] = {1, 0, 0, -1};

 

bool bfs(int sx, int sy, int gx, int gy)

{

memset(visited, 0, sizeof(visited));

if (sx == gx and sy == gy)

{

return true;

}

 

queue<pair<int, int>> q;

q.push({sx, sy});

visited[sx][sy] = true;

 

while (!q.empty())

{

auto cur = q.front();

q.pop();

int x = cur.first;

int y = cur.second;

 

for (int i = 0; i < 4; i++)

{

int nx = x + dx[i];

int ny = y + dy[i];

 

if (0 <= nx and nx < n and 0 <= ny and ny < m and mp[nx][ny] != '#')

{

if (visited[nx][ny] == false)

{

visited[nx][ny] = true;

if (nx == gx and ny == gy)

{

return true;

}

 

q.push({nx, ny});

}

}

}

}

return false;

}

int main()

{

cin >> n >> m;

int sx = 0, sy = 0;

int gx = 0, gy = 0;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

cin >> mp[i][j];

if (mp[i][j] == 'S')

{

sx = i;

sy = j;

}

if (mp[i][j] == 'T')

{

gx = i;

gy = j;

}

}

}

if (bfs(sx, sy, gx, gy)) cout << "mission passed respect+";

else cout << "wasted";

}