飞码网-免费源码博客分享网站

点击这里给我发消息

C++中的迷宫问题解决I

飞码网-免费源码博客分享网站 爱上飞码网—https://www.codefrees.com— 飞码网-matlab-python-C++ 爱上飞码网—https://www.codefrees.com— 飞码网-免费源码博客分享网站
假设有一个球在一个有空位和墙壁的迷宫中。现在小球可以通过向上、向下、向左、向右等任何方向滚动来穿过空路,但它不会停止滚动,直到撞上一堵墙。当小球停止时,它可以选择下一个方向。

我们要确定小球的起始位置、目的地和迷宫,我们要检查小球是否能在目的地停止。迷宫由一个二维数组来表示。这里1表示墙,0表示空的空间。迷宫的边界都是墙。起始点和目的地的坐标用行和列的指数表示。

因此,如果输入的内容就像一个由二维数组表示的迷宫一样。

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

开始位置是(0,4)目的位置是(4,4),那么输出将为真,一种可能的方法是--从左到下到右。

代码 

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool hasPath(vector<vector<int<>& grid, vector<int<& start, vector<int<& destination) {
      int n = grid.size();
      int m = grid[0].size();
      queue<vector<int< > q;
      q.push(start);
      set<vector<int< > visited;
      visited.insert(start);
      while (!q.empty()) {
         vector<int< curr = q.front();
         q.pop();
         int x = curr[0];
         int y = curr[1];
         if (destination[0] == x && destination[1] == y)
            return true;
         int i = x;
         while (i + 1 < n && !grid[i + 1][y])
            i++;
         if (!visited.count({ i, y })) {
            visited.insert({ i, y });
            q.push({ i, y });
         }
         i = x;
         while (i - 1 >= 0 && !grid[i - 1][y])
            i--;
         if (!visited.count({ i, y })) {
            visited.insert({ i, y });
            q.push({ i, y });
         }
         i = y;
         while (i + 1 < m && !grid[x][i + 1])
            i++;
         if (!visited.count({ x, i })) {
            visited.insert({ x, i });
            q.push({ x, i });
         }
         i = y;
         while (i - 1 >= 0 && !grid[x][i - 1])
            i--;
         if (!visited.count({ x, i })) {
            visited.insert({ x, i });
            q.push({ x, i });
         }
      }
      return false;
   }
};
main(){
   Solution ob;
   vector<vector<int<> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
   vector<int< v1 = {0,4}, v2 = {4,4};
   cout << (ob.hasPath(v, v1, v2));
}

输入

{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}},{0,4},{4,4}

输出

1
飞码网-免费源码博客分享网站 爱上飞码网—https://www.codefrees.com— 飞码网-matlab-python-C++ 爱上飞码网—https://www.codefrees.com— 飞码网-免费源码博客分享网站
赞 ()
内容页底部广告位3
留言与评论(共有 0 条评论)
   
验证码: