2 条题解

  • 2
    @ 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
      @ 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

      信息

      ID
      5804
      时间
      1000ms
      内存
      125MiB
      难度
      3
      标签
      递交数
      23
      已通过
      9
      上传者