BFS算法

#include<iostream>
#include<algorithm>
using namespace std;

#define N 15

char g[N][N];
int dist[N][N]; //存储每个点到起点的距离;
int n,m;
bool flag;
int ans = 0x3f3f3f3f; // 0x3f3f3f3f 作为无限大使用
int dx[4] ={1,-1,0,0},dy[4] ={0,0,-1,1}; //下 上 左 右;

void dfs(int x,int y)
{
    if(g[x][y]=='T')
    {   
        flag=true;
        ans =min(ans,dist[x][y]);
        return;
    }

    for(int i=0;i<4;i++)  
//如果中途进入下一环的dfs，在找到答案(不一定是最优解)之后，退回来会继续进行循环，称为：回溯！
    {
        int x1=x+dx[i],y1=y+dy[i];
        if(x1>=1 && x1<=n && y1>=1 && y1<=m && g[x1][y1] !='*')
        {
          if(dist[x][y] + 1 < dist[x1][y1])//这个条件并不是 说 这个点没有被走过 而是说 回溯时可以找到最优解
            {
                dist[x1][y1] = dist[x][y] + 1;
                dfs(x1,y1);
            }
        }

    }

}

int main()
{
    int x,y; cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
            dist[i][j] = 1e3;
            if(g[i][j]=='S') //char
            {
                x=i,y=j;
            }
        }
    }
    dist[x][y] = 0;
    dfs(x,y);
    if(flag)
    printf("%d",ans);
    else
    printf("-1");

    return 0;
 } 

BFS算法

DFS 算法

#include<iostream>
#include<algorithm>
using namespace std;

#define N 25

char g[N][N];
int dist[N][N];
int n,m;
bool flag;
int ans = 0x3f3f3f3f;
int dx[4] ={1,-1,0,0},dy[4] ={0,0,-1,   1};

void dfs(int x,int y)
{
    if(x==1||y==1||x==n||y==m)
    {
        flag=true;
        ans =min(ans,dist[x][y]);
        return;
    }

    for(int i=0;i<4;i++)
    {
        int x1=x+dx[i],y1=y+dy[i];
        if(x1>=1 && x1<=n && y1>=1 && y1<=m && g[x1][y1] !='#')
        {
            if(dist[x][y] + 1 < dist[x1][y1])
            {
                dist[x1][y1] =dist[x][y] + 1;
                dfs(x1,y1);
            }
        }

    }

}

int main()
{
    int x,y; cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
            dist[i][j] = 1e3;
            if(g[i][j]=='@')
            {
                x=i,y=j;
            }
        }
    }
    dist[x][y] = 0;
    dfs(x,y);
    if(flag)
    printf("%d",ans);
    else
    printf("-1");

    return 0;
 } 

BFS 算法

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N  = 25;
char g[N][N];
int n,m;
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
typedef pair<int,int> PII;
int dist[N][N];

int bfs(int x,int y)
{

    memset(dist,0x3f,sizeof dist);
    queue<PII> q;
    dist[x][y] = 0;
    q.push({x , y});

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i=0;i<4;i++)
        {
            int x1=t.first + dx[i],y1=t.second + dy[i];
            if(x1 >=1 && x1<=n && y1>=1 && y1<=m && g[x1][y1] !='#' &&  dist[x1][y1] == 0x3f3f3f3f)
            {
                dist[x1][y1] =dist[t.first][t.second] +1;
                q.push({x1,y1});
            }
            if(g[x1][y1] =='.' && (x1 ==1 || x1==n || y1==1 || y1==m))
                return dist[x1][y1];
        }
    }

    return 0x3f3f3f3f;
}

int main()
{
    int x,y;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
            if(g[i][j]=='@')
            {
                x=i,y=j;
            }
        }    


    if(bfs(x,y) == 0x3f3f3f3f)
        printf("-1\n");
    else
        printf("%d\n",bfs(x,y));


    return 0;
}