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;
    }
    

    Information

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