首页 > 代码库 > 【HDU1198】Farm Irrigation(回溯+记忆化搜索)
【HDU1198】Farm Irrigation(回溯+记忆化搜索)
数据流小,深搜即可。有些暴力。看其他人的题解用二维转换成一维做的并查集很巧妙,马上去研究一下!!
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。