2 条题解

  • 0
    @ 2025-2-23 16:05:45
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 200;
    int T;
    int n, m;
    char a[MAXN + 5][MAXN + 5];
    // 起点到 (i,j) 的最短路程
    int dis[MAXN + 5][MAXN + 5];
    // 表示有没有走过每个位置(也可以用 dis 为 -1 代替)
    bool vis[MAXN + 5][MAXN + 5];
    // 记录起点终点
    int sx, sy, ex, ey;
    // 方向数组
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    queue<int> qx, qy;
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> T;
        while (T--)
        {
            cin >> n >> m;
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                {
                    cin >> a[i][j];
                    if (a[i][j] == 'S')
                        sx = i, sy = j;
                    if (a[i][j] == 'E')
                        ex = i, ey = j;
                }
            // 多测要清空
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    vis[i][j] = false;
            while (!qx.empty())
                qx.pop();
            while (!qy.empty())
                qy.pop();
            // 广搜走迷宫
            vis[sx][sy] = true;
            dis[sx][sy] = 0;
            qx.push(sx);
            qy.push(sy);
            while (!qx.empty() && !vis[ex][ey])
            {
                int x = qx.front();
                int y = qy.front();
                qx.pop();
                qy.pop();
                for (int i = 0; i < 4; i++)
                {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (1 <= nx && nx <= n &&
                        1 <= ny && ny <= m &&
                        a[nx][ny] != '#' &&
                        !vis[nx][ny])
                    {
                        vis[nx][ny] = true;
                        dis[nx][ny] = dis[x][y] + 1;
                        qx.push(nx);
                        qy.push(ny);
                    }
                }
            }
            if (!vis[ex][ey])
                cout << "oop!\n";
            else
                cout << dis[ex][ey] << "\n";
        }
        return 0;
    }
    
    • -4
      @ 2022-11-8 16:28:07

      广搜

      #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;
      }
      

      迭代加深搜索版

      • 1

      信息

      ID
      475
      时间
      1000ms
      内存
      128MiB
      难度
      4
      标签
      (无)
      递交数
      110
      已通过
      49
      上传者