迷宫收集星星并查集解答

群里发的来历不明的题目可使用深搜广搜解决我试了试并查集效率不是很高

题目描述

解答并查集

  1 #include <iostream>
  2 #include <vector>
  3 
  4 
  5 using namespace std;
  6 const int maxn = 1e5 + 7;
  7 int pre[maxn];
  8 
  9 int Find(int x)
 10 {
 11     int p, tmp;
 12     p = x;
 13     while (x != pre[x])
 14         x = pre[x];
 15     while (p != x)
 16     {
 17         tmp = pre[x];
 18         pre[x] = x;
 19         p = tmp;
 20     }
 21     return x;
 22 }
 23 
 24 void join(int x, int y)
 25 {
 26     int fx = Find(x);
 27     int fy = Find(y);
 28     if (fx != fy)
 29         pre[fx] = fy;
 30 }
 31 
 32 bool Same(int x, int y)
 33 {
 34     return Find(x) == Find(y);
 35 }
 36 
 37 
 38 int m = 4; int n = 8;
 39 
 40 vector<vector<char>> vmap(4, vector<char>(8, '.'));
 41 
 42 void Init()
 43 {
 44     vmap[0][2] = '#';
 45     vmap[0][6] = '*';
 46 
 47     vmap[1][0] = '*';
 48     vmap[1][2] = '#';
 49     vmap[1][4] = 'S';
 50     vmap[1][5] = '#';
 51 
 52     vmap[2][0] = '#';
 53     vmap[2][1] = '#';
 54     vmap[2][2] = '#';
 55     vmap[2][3] = '#';
 56     vmap[2][4] = '#';
 57     vmap[2][5] = '#';
 58 
 59     vmap[3][1] = '*';
 60     vmap[3][4] = '#';
 61     vmap[3][6] = '*';
 62 
 63     for (int i = 0; i < 4; i++) {
 64         for (int j = 0; j < 8; j++) {
 65             cout << vmap[i][j] << " ";
 66         }
 67         cout << endl;
 68     }
 69 
 70     for (int i = 0; i < maxn; i++) {
 71         pre[i] = i;
 72     }
 73          
 74 
 75 }
 76 
 77 int GetId(int x, int y)
 78 {
 79     return (x +1)* 10 + (y+1);
 80 }
 81 
 82 int main()
 83 {
 84     //std::cout << "Hello World!
"; 
 85     Init();
 86     int myId = -1;
 87     vector<int> record;
 88     for (int i = 0; i < 4; i++) {
 89         for (int j = 0; j < 8; j++) {
 90             if (vmap[i][j] == '#')
 91                 continue;
 92 
 93             if ((i + 1) < 4 && vmap[i+1][j] != '#') {
 94                 int Id = GetId(i, j);
 95                 int Id1 = GetId(i + 1, j);
 96                 join(Id ,Id1);
 97             }
 98             
 99             if ((j + 1) < 8 && vmap[i][j+1] != '#')
100             {
101                 int Id = GetId(i, j);
102                 int Id1 = GetId(i , j+1);
103                 join(Id, Id1);
104 
105             }
106              
107             if ((i - 1) > 0 && vmap[i - 1][j] != '#') {
108                 int Id = GetId(i, j);
109                 int Id1 = GetId(i - 1, j);
110                 join(Id, Id1);
111             
112             }
113             
114             if ((j - 1) > 0 && vmap[i][j - 1] != '#') {
115                 int Id = GetId(i, j);
116                 int Id1 = GetId(i , j-1);
117                 join(Id, Id1);
118             }
119 
120             if (vmap[i][j] == '*') {
121                 record.push_back(GetId(i,j));
122             }
123             else if (vmap[i][j] == 'S') {
124                 myId = GetId(i, j);
125             }
126         }
127     }
128     int count = 0;
129     for (auto& e : record) {
130         if (Same(e, myId)) {
131             count++;
132         }
133     }
134     cout << count;
135 }

View Code

作者: itdef
欢迎转帖请保持文本完整并注明出处
技术博客 http://www.cnblogs.com/itdef/
B站算法视频题解
https://space.bilibili.com/18508846
qq 151435887
gitee https://gitee.com/def/
欢迎c c++ 算法爱好者 windows驱动爱好者服务器程序员沟通交流
如果觉得不错，欢迎点赞，你的鼓励就是我的动力
阿里打赏

迷宫收集星星 并查集解答

迷宫收集星星并查集解答