7 solutions

  • 1
    @ 2024-3-27 11:06:37 
    #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
      @ 2024-3-26 19:28:55 
      #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
        @ 2024-3-15 22:07:12 
        #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
          @ 2022-1-28 12:15:35 
          #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
            @ 2023-4-7 19:51:19

            稀里糊涂就过了，哈哈哈，祝大家好运，对了，那个起点要特判一下哦，注意了

            #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
              @ 2022-12-31 15:41:59

              #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
                @ 2022-3-30 20:50:28
                • 注意要特判起点和终点是否是可通行的，不然有一个测试点过不了
                #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
                877
                Accepted
                162
                Uploaded By
                1. About
                2. Contact Us
                3. Privacy
                4. Terms of Service
                5. Copyright Complaint
                6. Language
                7. Legacy mode
                8. Theme
                2. 蜀ICP备2021003932号-1
                3. Worker 0, 16ms
                4. Powered by Hydro v4.11.1 Community