3 solutions

  • 1
    @ 2024-3-16 21:25:14
    #include<iostream>
    #include<queue>
    using namespace std;
    struct Point
    {
    	int x;	//用结构体表示此时坐标和已走步数
    	int y;
    	int step;
    };
    void bfs();
    int R, C;
    char mp[105][105];
    bool vis[105][105] = {};
    queue<Point> q;
    int main()
    {
    	cin >> R >> C;
    	for (int i = 1; i <= R; i++)
    		for (int j = 1; j <= C; j++)
    
    			cin >> mp[i][j];
    	q.push({ 1,1,1 });
    	bfs();
    	return 0;
    }
    void bfs()
    {
    	int x, y;		
    	Point p;
    	int dx[4] = {0,0,1,-1};
    	int dy [4] = {1,-1,0,0};
    	while(!q.empty())
    	{
    		p = q.front();
    		q.pop();
    		if (p.x == C && p.y == R)
    		{
    			cout << p.step;
    			return;
    		}
    		if (vis[p.x][p.y])
    			continue;
    		vis[p.x][p.y] = true;
    		for (int i = 0; i < 4; i++)
    		{
    			x = p.x + dx[i];
    			y = p.y + dy[i];
    			if (x > 0 && x <= C && y > 0 && y <= R && vis[x][y] == false && mp[x][y] == '.')
    				q.push({ x,y,p.step + 1 });
    		}
    	}
    	cout << -1 << endl;
    }
    
    • 0
      @ 2022-12-30 21:09:06

      #include<bits/stdc++.h> using namespace std; const int N=1e2+10; char maze[N][N]; int vis[N][N]; int dirx[]={0,0,-1,1}; int diry[]={-1,1,0,0}; int n,m; struct node1{ int x,y,w; }; queueque; bool check(int x,int y) { if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]0&&maze[x][y]'.') return true; return false; } int bfs() { que.push({0,0,1}); while(!que.empty()) { node1 p=que.front(); que.pop(); if(p.xn-1&&p.ym-1) return p.w ; if(vis[p.x][p.y]) continue; vis[p.x][p.y]=true; for(int i=0;i<4;i++) { int nx=dirx[i]+p.x; int ny=diry[i]+p.y; if(check(nx,ny)) que.push({nx,ny,p.w+1}); } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>maze[i][j]; cout<<bfs()<<endl; return 0; }

      • 0
        @ 2022-3-24 23:00:57
        #include <stdio.h>
        #include <math.h>
        #include <algorithm>
        #include <iostream>
        #include <string.h>
        #include <queue>
        #include <stack>
        #include <map>
        #include <set>
        #include <vector>
        using namespace std;
        int n,m;
        char a[45][45];
        int vis[45][45];
        struct temp {
            int tx;
            int ty;
            int step;
        };
        int nx[4]= {0,0,1,-1};
        int ny[4]= {1,-1,0,0};
        queue<temp> q;
        void bfs() {
            while(!q.empty()) {
                temp t=q.front();
                q.pop();
                if(t.tx==n-1&&t.ty==m-1) {
                    cout<<t.step;
                    return;
                }
                if(vis[t.tx][t.ty])
                    continue;
                vis[t.tx][t.ty]=1;
                for(int i=0; i<4; i++) {
                    int x=t.tx+nx[i],y=t.ty+ny[i];
                    if(x>=0&&y>=0&&x<n&&y<m&&vis[x][y]==0&&a[x][y]=='.')
                        q.push({x,y,t.step+1});
                }
            }
        }
        int main() {
            scanf("%d%d",&n,&m);
            for(int i=0; i<n; i++) {
                cin>>a[i];
            }
            q.push({0,0,1});
            bfs();
            return 0;
        }
        
        • 1

        Information

        ID
        769
        Time
        1000ms
        Memory
        128MiB
        Difficulty
        7
        Tags
        # Submissions
        444
        Accepted
        87
        Uploaded By