7 solutions
-
1
#include<iostream> #include<vector> #include<queue> using namespace std; int n; vector<vector<int>> maze; vector<vector<bool>> visited; struct Position { int x, y; }; int dirX[4] = {0, 1, 0, -1}; int dirY[4] = {1, 0, -1, 0}; bool bfs(int startX, int startY, int endX, int endY) { if (maze[startX][startY] == 1 || maze[endX][endY] == 1) { return false; // 起点或终点不可通行 } queue<Position> q; q.push({startX, startY}); visited[startX][startY] = true; while (!q.empty()) { Position current = q.front(); q.pop(); if (current.x == endX && current.y == endY) { return true; } for (int i = 0; i < 4; i++) { int nextX = current.x + dirX[i]; int nextY = current.y + dirY[i]; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0 && !visited[nextX][nextY]) { visited[nextX][nextY] = true; q.push({nextX, nextY}); } } } return false; } int main() { cin >> n; int startX, startY, endX, endY; maze.resize(n, vector<int>(n)); visited.resize(n, vector<bool>(n, false)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> maze[i][j]; } } cin >> startX >> startY >> endX >> endY; startX--; startY--; endX--; endY--; // 转换为从0开始的索引 if (bfs(startX, startY, endX, endY)) { cout << "YES" << endl; } else { cout << "NO" << endl; } }
-
1
#include <iostream> #include <vector> using namespace std; int n; // 迷宫的规模 vector<vector<int>> maze; // 迷宫矩阵 vector<vector<bool>> visited; // 访问状态记录 // 四个方向移动的坐标变化:上、下、左、右 int dirX[4] = {-1, 1, 0, 0}; int dirY[4] = {0, 0, -1, 1}; bool isValid(int x, int y) { if (x < 0 || y < 0 || x >= n || y >= n) return false; // 越界检查 if (maze[x][y] == 1) return false; // 墙壁检查 if (visited[x][y]) return false; // 已访问检查 return true; } bool dfs(int x, int y, int er, int el) { if (!isValid(x, y)) return false; if (x == er && y == el) return true; // 到达终点 visited[x][y] = true; // 标记当前位置已访问 for (int i = 0; i < 4; i++) { // 尝试四个方向 int nextX = x + dirX[i]; int nextY = y + dirY[i]; if (dfs(nextX, nextY, er, el)) { return true; // 找到一条路径 } } return false; } int main() { cin >> n; maze.resize(n, vector<int>(n)); // 根据迷宫规模初始化迷宫矩阵 visited.resize(n, vector<bool>(n, false)); // 初始化访问状态记录 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> maze[i][j]; } } int sr, sl, er, el; cin >> sr >> sl >> er >> el; sr--; sl--; er--; el--; // 转换为以0为起始的索引 if (maze[sr][sl] == 1 || maze[er][el] == 1) { cout << "NO" << endl; } else if (dfs(sr, sl, er, el)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }
-
1
#include<iostream> using namespace std; void dfs(int x, int y); bool check(int nx, int ny); int n, mp[105][105], ha, la, hb, lb; bool vis[105][105] = {}, flag = false; int main() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> mp[i][j]; cin >> ha >> la >> hb >> lb; if (mp[ha][la] == 1) { cout << "NO" << endl; return 0; } dfs(ha, la); if (flag) cout << "YES" << endl; else cout << "NO" << endl; return 0; } void dfs(int x, int y) { int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int nx, ny; if (vis[x][y] || flag) return; vis[x][y] = true; if (x == hb && y == lb) { flag = true; return; } for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (check(nx,ny)) dfs(nx, ny); } } bool check(int nx,int ny) { if (nx > 0 && nx <= n && ny > 0 && ny <= n && vis[nx][ny] == false && mp[nx][ny] == 0) return true; return false; }
-
1
#include <bits/stdc++.h> using namespace std; #define endl printf("\n") int n,xx,yy,xx1,yy1; bool s[103][103],flag; int x2[4]={0,1,0,-1},y2[4]={1,0,-1,0}; int ss[104][104]; bool check(int x,int y){ return (x>=1&&x<=n&&y>=1&&y<=n&&!s[x][y]); } void dfs(int x,int y){ if(x==xx1&&y==yy1){ flag=1; return ; } for(int i=0;i<=3;i++){ int xx=x+x2[i],yy=y+y2[i]; if(check(xx,yy)&&ss[xx][yy]==0){ s[xx][yy]=1; dfs(xx,yy); } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>ss[i][j]; } } cin>>xx>>yy>>xx1>>yy1; s[xx][yy]=1; if(!ss[xx][yy]) dfs(xx,yy); if(!flag) puts("NO\n"); else puts("YES\n"); return 0; }
-
0
稀里糊涂就过了,哈哈哈,祝大家好运,对了,那个起点要特判一下哦,注意了
#include<iostream> using namespace std; const int N=1e2+10; int n; int sx,sy,ex,ey; int map[N][N]; int vis[N][N]={0}; int dx[4]={-1,0,1,0}; int dy[4]={0,-1,0,1}; void dfs(int x,int y) { if(x>=n&&y>=n) return; if(x==ex&&y==ey) { cout<<"YES"; return; } if(vis[x][y]==1) return; vis[x][y]=1; for(int i=0;i<4;i++) { int xx=dx[i]+x; int yy=dy[i]+y; if(vis[xx][yy]!=1&&xx>0&&xx<=n&&yy>0&&yy<=n) { vis[xx][yy]=1; dfs(xx,yy); vis[xx][yy]=0; } } cout<<"NO"; } int main() { //cout<<N; cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>map[i][j]; } } cin>>sx>>sy>>ex>>ey; map[sx][sy]=1; dfs(sx,sy); return 0; }
-
0
#include<bits/stdc++.h> using namespace std; /* 将字符串的空格变成“%20” int main() { string a; getline(cin,a); for(int i=0;i<a.size();++i) { if(a[i]' ') a.replace(i,1,"%20"); } cout<<a; } */ bool fd=false; const int N=1e3+10; int dirx[]={0,0,-1,1}; int diry[]={-1,1,0,0}; int maze[N][N]; int vis[N][N]; int n; int sx,sy,ex,ey; bool check(int x,int y) { if(x<=n&&x>=1&&y<=n&&y>=1&&!vis[x][y]&&maze[x][y]0) return true; return false; } void dfs(int x,int y) { if(vis[x][y]) //访问过了。返回 return ; vis[x][y]=true; if(xn&&yn) { fd=true; return ; } for(int i=0;i<4;i++) { int tx=x+dirx[i]; int ty=y+diry[i]; if(check(tx,ty)) dfs(tx,ty); } return ; } int main(){ cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>maze[i][j]; cin>>sx>>sy>>ex>>ey; dfs(sx,sy); if(maze[sx][sy]==1||maze[ex][ey]==1) fd=false; puts(fd? "YES":"NO"); return 0; }
-
0
- 注意要特判起点和终点是否是可通行的,不然有一个测试点过不了
#include <iostream> using namespace std; const int N=101; int a[N][N],ma[N][N]; int n,sx,sy,fx,fy,nex,ney,ans; int opx[5]={1,-1,0,0}; int opy[5]={0,0,1,-1}; void dfs(int x,int y) { if(x==fx&&y==fy) ans++; else{ for(int i=0;i<4;i++) { nex=x+opx[i]; ney=y+opy[i]; if(nex>=1&&nex<=n&&ney>=1&&ney<=n&&ma[nex][ney]==0) { ma[nex][ney]=1; dfs(nex,ney); ma[nex][ney]=0; } } } } int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>a[i][j]; if(a[i][j]==1) ma[i][j]=1; } } cin>>sx>>sy>>fx>>fy; if(ma[sx][sy]==1||ma[fx][fy]==1) { cout<<"NO"<<endl; } else { dfs(sx,sy); if(ans==0) { cout<<"NO"<<endl; } else{ cout<<"YES"<<endl; } } return 0; }
- 1
Information
- ID
- 767
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 8
- Tags
- # Submissions
- 927
- Accepted
- 165
- Uploaded By