题解
【基础】迷宫出口
3 条题解
-
0
#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
#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
#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