广搜

#include <bits/stdc++.h>
using namespace std;
int T;
int n, m;
char g[205][205];
int sx, sy, ex, ey;
//广搜
bool vis[205][205];
int dis[205][205];
queue<int> qx;
queue<int> qy;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void bfs(int sx, int sy, int ex, int ey)
{
    // init
    while (!qx.empty())
        qx.pop();
    while (!qy.empty())
        qy.pop();
    memset(vis, false, sizeof(vis));
    memset(dis, 0, sizeof(dis));
    // 起点入队
    qx.push(sx);
    qy.push(sy);
    vis[sx][sy] = true;
    dis[sx][sy] = 0;
    while (!qx.empty() && !vis[ex][ey])
    {
        int nowX = qx.front();
        qx.pop();
        int nowY = qy.front();
        qy.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = nowX + dx[i];
            int ny = nowY + dy[i];
            if (!vis[nx][ny] &&
                g[nx][ny] != '#')
            {
                qx.push(nx);
                qy.push(ny);
                vis[nx][ny] = true;
                dis[nx][ny] = dis[nowX][nowY] + 1;
            }
        }
    }
    if (!vis[ex][ey])
        cout << "oop!\n";
    else
        cout << dis[ex][ey] << "\n";
}
int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        memset(g, '#', sizeof(g));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                cin >> g[i][j];
                if (g[i][j] == 'S')
                    sx = i, sy = j, g[i][j] = '.';
                if (g[i][j] == 'E')
                    ex = i, ey = j, g[i][j] = '.';
            }
        bfs(sx, sy, ex, ey);
    }
    return 0;
}

深搜超时版

#include<bits/stdc++.h>
using namespace std;
int T,n,m;
char g[205][205];
int sx, sy, ex, ey;
int dis[205][205];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int nx = x+dx[i];
		int ny = y+dy[i];
		if(g[nx][ny]!='#'&&dis[nx][ny]>dis[x][y]+1){
			dis[nx][ny] = dis[x][y]+1;
			dfs(nx,ny);
		}
	}
}
int main()
{
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=0;i<=n+1;i++)
			g[i][0]=g[i][m+1]='#';
		for(int i=0;i<=m+1;i++)
			g[0][i]=g[n+1][i]='#';
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				{
					cin>>g[i][j];
					dis[i][j]=40005;
					if(g[i][j]=='S'){
						sx=i,sy=j;
						g[i][j] = '.';
					}
					if(g[i][j]=='E'){
						ex=i,ey=j;
						g[i][j] = '.';
					}
				}
		dis[sx][sy] = 0;
		dfs(sx,sy);
		/*
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)
				cout<<dis[i][j]<<" ";
			cout<<"\n";
		}
		*/
		if(dis[ex][ey]!=40005)	
			cout<<dis[ex][ey]<<"\n";
		else
			cout<<"oop!\n";	
	}
	return 0;
}

迭代加深搜索版

略