top1编程
← 返回题目
题解

【基础】迷宫出口

3 条题解

  • 0
    @ 2026-7-29 20:22:19
    #include <bits/stdc++.h>
    using namespace std;
    
    int n, a[105][105];
    int ha, la, hb, lb;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    
    bool dfs(int x, int y) {
        if (x == hb && y == lb) return true;
        a[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 1 && nx <= n &&
                ny >= 1 && ny <= n && a[nx][ny] == 0) {
                if (dfs(nx, ny)) return true;
            }
        }
        return false;
    }
    
    int main() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) cin >> a[i][j];
        }
        cin >> ha >> la >> hb >> lb;
        if (a[ha][la] == 1 || a[hb][lb] == 1) cout << "NO";
        else cout << (dfs(ha, la) ? "YES" : "NO");
        return 0;
    }
    
    • 0
      @ 2026-7-29 0:06:21
      #include <bits/stdc++.h>
      using namespace std;
      
      int n, a[105][105];
      int ha, la, hb, lb;
      int dx[4] = {1, -1, 0, 0};
      int dy[4] = {0, 0, 1, -1};
      
      bool dfs(int x, int y) {
          if (x == hb && y == lb) return true;
          a[x][y] = 1;
          for (int i = 0; i < 4; i++) {
              int nx = x + dx[i];
              int ny = y + dy[i];
              if (nx >= 1 && nx <= n &&
                  ny >= 1 && ny <= n && a[nx][ny] == 0) {
                  if (dfs(nx, ny)) return true;
              }
          }
          return false;
      }
      
      int main() {
          cin >> n;
          for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= n; j++) cin >> a[i][j];
          }
          cin >> ha >> la >> hb >> lb;
          if (a[ha][la] == 1 || a[hb][lb] == 1) cout << "NO";
          else cout << (dfs(ha, la) ? "YES" : "NO");
          return 0;
      }
      
      • 0
        @ 2026-7-28 22:09:21
        #include <iostream>
        using namespace std;
        
        int a[150][150],n,x1,y1,x2,y2;
        bool f = false;//表示有没有走到 
        
        //从x、y点开始逐步探测 
        void num(int x,int y){
        	if(x == x2 && y == y2){
        		f = true;
        	}else{
        		a[x][y] = 1;//探测过的点,设置为不可探测,防止重复的探测 
        		//上下左右探测,且不越界 
        		if(x - 1 >= 1 && a[x - 1][y] == 0) num(x-1,y);
        		if(x + 1 <= n && a[x + 1][y] == 0) num(x+1,y);
        		if(y - 1 >= 1 && a[x][y - 1] == 0) num(x,y - 1);
        		if(y + 1 <= n && a[x][y + 1] == 0) num(x,y + 1);
        	}
        } 
        
        int main(){
        	int i,j;
        	cin>>n;
        	//0表示能走,1表示不能走 
        	for(i = 1;i <= n;i++){
        		for(j = 1;j <= n;j++){
        			cin>>a[i][j];
        		}
        	}
        	cin>>x1>>y1>>x2>>y2;
        	
        	//如果起止点有1,则不需要探测 
        	if(a[x1][y1] == 1 || a[x2][y2] == 1){
        		cout<<"NO"<<endl; 
        	}else{
        		num(x1,y1);
        		//探测完测试,如果走到了 
        		if(f == true){
        			cout<<"YES"<<endl; 
        		}else{
        			cout<<"NO"<<endl;
        		}
        	} 
        }
        
        • 1