2 条题解

  • 2
    @ 2025-3-8 13:05:14
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e3+5;
    char a[N][N];
    int vis[N][N];
    int n,m,sx,sy,fx,fy;
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    struct point{
    	int x,y;
    };
    queue <point> q;
    int bfs(int x,int y){
    	point p={x,y};
    	q.push(p);
    	while(!q.empty()){
    		point temp=q.front();
    		q.pop();
    		if(temp.x==fx && temp.y==fy) return vis[temp.x][temp.y]-1;
    		else{
    			for(int i=0;i<4;i++){
    				point np=temp;
    				np.x+=dx[i];
    				np.y+=dy[i];
    				if(np.x>=1 && np.x<=n && np.y>=1 && np.y<=n && a[np.x][np.y]=='0' && vis[np.x][np.y]==0){
    					q.push(np);
    					vis[np.x][np.y]=vis[temp.x][temp.y]+1;
    				}
    			}
    		}
    	}
    }
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			cin>>a[i][j];
    		}
    	}
    	cin>>sx>>sy>>fx>>fy;
    	vis[sx][sy]=1;
    	cout<<bfs(sx,sy)<<endl;
    	return 0;
    }
    • 1
      @ 2025-3-2 15:18:24

      注意!!

      狡猾的y1函数会伪装成变量诱导你

      实在可恶!!!

      #include <bits/stdc++.h>
      using namespace std;
      int n;
      char a[1007][1007];
      int x1, y11, x2, y2;
      struct node {
          int x;
          int y;
          int steps;
      };
      int xo[4] = {1, 0, 0, -1};  //x方向
      int yo[4] = {0, -1, 1, 0};  //y方向
      queue<node> op;
      int minstep = 99999999;  //初始化为一个很大的值
      //BFS
      void bfs(int x1, int y1) {
          //检查起点和终点是否是障碍物
          if (a[x1][y11] == '1' || a[x2][y2] == '1') {
              minstep = -1;  //是障碍,无法到达
              return;
          }
          op.push(node{x1, y11, 0});
          a[x1][y1] = '1';  // 标记起点为已访问
          while (!op.empty()) {
              node tou = op.front();
              op.pop();
              if (tou.x == x2 && tou.y == y2) {
                  minstep = tou.steps;
                  return;  // 找到目标点,提前返回
              }
              // 遍历四个方向
              for (int i = 0; i < 4; i++) {
                  int xx = tou.x + xo[i];
                  int yy = tou.y + yo[i];
                  // 检查越界和是否访问过 
                  if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] == '0') {
                      a[xx][yy] = '1';  // 标记该位置为已访问
                      op.push(node{xx, yy, tou.steps + 1});
                  }
              }
          }
      }
      int main() {
          cin >> n;
          for (int i = 0; i < n; i++) {
              for (int j = 0; j < n; j++) {
                  cin >> a[i][j];
              }
          }
          cin >> x1 >> y11 >> x2 >> y2;
          x1--; y11--; x2--; y2--;  // 坐标从1开始,转换为从0开始的索引
          bfs(x1, y11);
          // 如果 minstep 仍是初始值,表示没有找到路径
          if (minstep == 99999999) {
              cout << "-1" << endl;  // 无法到达目标(好像有点多余,题里头没要求)
          } else {
              cout << minstep;  // 输出最短路径的步数
          }
          return 0;
      }
      //bfs真好玩!! 
      
      
      • 1

      信息

      ID
      5804
      时间
      1000ms
      内存
      125MiB
      难度
      2
      标签
      递交数
      20
      已通过
      7
      上传者