首页 > 代码库 > 【HDU1198】Farm Irrigation（回溯+记忆化搜索）

【HDU1198】Farm Irrigation（回溯+记忆化搜索）

2024-07-14 03:33:47   224人阅读

数据流小，深搜即可。有些暴力。看其他人的题解用二维转换成一维做的并查集很巧妙，马上去研究一下！！

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <numeric> 9 #include <string>10 #include <limits.h>11 #include <map>12 using namespace std;13 14 int m, n, ans = 0;15 char Map[55][55];16 bool vis[55][55];17 map<char, string> check;18 19 void dfs (int x, int y) {20 21     vis[x][y] = 1;22 23     if (check[Map[x][y]].find("U") != -1 && check[Map[x - 1][y]].find("D") != -1) {24         if (!vis[x - 1][y]) dfs (x - 1, y);25     }26 27     if (check[Map[x][y]].find("D") != -1 && check[Map[x + 1][y]].find("U") != -1) {28         if (!vis[x + 1][y]) dfs (x + 1, y);29     }30 31     if (check[Map[x][y]].find("L") != -1 && check[Map[x][y - 1]].find("R") != -1) {32         if (!vis[x][y - 1]) dfs (x, y - 1);33     }34 35     if (check[Map[x][y]].find("R") != -1 && check[Map[x][y + 1]].find("L") != -1) {36         if (!vis[x][y + 1]) dfs (x, y + 1);37     }38 }39 40 int main () {41 42     check[‘A‘] = "UL";  check[‘B‘] = "UR";  check[‘C‘] = "DL";43     check[‘D‘] = "DR";  check[‘E‘] = "UD";  check[‘F‘] = "LR";44     check[‘G‘] = "ULR"; check[‘H‘] = "UDL"; check[‘I‘] = "DLR";45     check[‘J‘] = "UDR"; check[‘K‘] = "UDLR";46 47     while (~scanf("%d%d", &m, &n)) {48         if (m < 0 && n < 0) {49             break;50         }51         memset (vis, 0, sizeof(vis));52         memset (Map, 0, sizeof(Map));53         for (int i = 0; i < m ; ++ i) {54             for (int j = 0 ; j < n; ++ j) {55                 cin >> Map[i][j];56             }57         }58         ans = 0;59         for (int i = 0; i < m; ++ i) {60             for (int j = 0; j < n; ++j) {61                 if (vis[i][j] != 1) {62                     dfs (i, j);63                     ans ++;64                 }65             }66         }67 68         cout << ans << endl;69     }70     return 0;71 }

 


联系
我们