摘要:本文主要向大家介绍了C++语言如何实现DFS之“农田灌溉”,通过具体的代码向大家展示,希望对大家学习C++语言有所帮助。
本文主要向大家介绍了C++语言如何实现DFS之“农田灌溉”,通过具体的代码向大家展示,希望对大家学习C++语言有所帮助。
这也是一道利用了DFS的题目,先说下我的思路:用一个二维数组记录每个字母所代表的含义(管道方向),用另一个二维数组记录4个方向的变换坐标;随后利用经典的DFS递归遍历即可~(还要注意在方向的处理上前后要保持一致,否则很容易计算出错 :| )
农田灌溉(Farm Irrigation)
题目描述:
Benny有一大片农田需要灌溉。农田是一个长方形,被分割成许多小的正方形。每个正方形中都安装了水管。不同的正方形农田中可能安装了不同的水管。一共有11种水管,分别用字母A~K标明,如图1所示。
Benny农田的地图是由描述每个正方形农田中水管类型的字母组成的矩阵。例如,如果农田的地图为: ADC FJK IHE
则农田中水管分布如图2所示。
某些正方形农田的中心有水源,因此水可以沿着水管从一个正方形农田流向另一个正方形农田。如果水可以流经某个正方形农田,则整个正方形农田可以全部灌溉到。 Benny想知道至少需要多少个水源,以保证整个农田都能被灌溉到? 例如,图2所示的农田至少需要3个水源,图中的圆点表示每个水源。
输入描述:
输入文件中包含多个测试数据。每个测试数据的第1行为两个整数M和N,表示农田中有M行,每行有N个正方形。接下来有M行,每行有N个字符。字符的取值为'A'~'K',表示对应正方形农田中水管的类型。当M或N取负值时,表示输入文件结束。如果M和N的值为正数,则其取值范围是1≤M, N≤50。
输出描述:
对输入文件中的每个测试数据所描述的农田,输出占一行,为求得的所需水源数目的最小值。
样例输入:
2 2
DK
HF
3 3
ADC
FJK
IHE
-1 -1
样例输出:
2 3
闲话少叙,直接上代码+注释~
Code:
[cpp] view plain copy 1. #include<iostream> 2. using namespace std; 3. 4. #define MAXN 50 5. char map[MAXN][MAXN]; //地图 6. int M, N; //M:农田行数,N:每行的正方形个数 7. 8. int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; //管道坐标变换的四个方向:对应的顺序上下左右。 9. int dirO[11][4] = { 10. {-1, 0, -1, 0}, {-1, 0, 0, 1}, {0, 1, -1, 0}, 11. {0, 1, 0, 1}, {-1, 1, 0, 0}, {0, 0, -1, 1}, 12. {-1, 0, -1, 1}, {-1, 1, -1, 0}, {0, 1, -1, 1}, 13. {-1, 1, 0, 1}, {-1, 1, -1, 1} 14. }; //每种农田块对应的4个管道方向(-1为左或上、1为右或下、0为没有)。 15. 16. void DFS(int x, int y) 17. { 18. int xx, yy; 19. char temp = map[x][y]; //暂存当前农田块的形状,便于后面的比较~ 20. map[x][y] = 'Y'; //覆盖原来农田为已遍历 21. for(int i = 0; i < 4; i++) 22. { 23. //计算下一个方向的坐标。 24. xx = x + dir[i][0]; 25. yy = y + dir[i][1]; 26. if(xx<0 || xx>=MAXN || yy<0 || yy>=MAXN) continue; //越界,跳至下一个方向的判断 27. 28. //方向所代表的值:上0、下1、左2、右3。 29. 30. //如果向上走(0)或向左走(2),比如向左走则判断原坐标的“左”管道和下一个方向坐标的“右”管道,方向所代表的值+1 31. if(i == 0 || i == 2) 32. {//若相邻两块农田管道能“接上”,即管道方向对应的值之积为-1 33. if(map[xx][yy]!='Y' && dirO[temp-'A'][i]*dirO[map[xx][yy]-'A'][i+1]==-1) DFS(xx, yy); 34. } 35. //否则为向下走(1)或向右走(3),比如向下走则判断原坐标的“下”管道和下一个方向坐标的“上”管道。对应方向所代表的值-1 36. else if(map[xx][yy]!='Y' && dirO[temp-'A'][i]*dirO[map[xx][yy]-'A'][i-1]==-1) DFS(xx, yy); 37. } 38. } 39. int main() 40. { 41. int i, j; 42. int count; 43. while(scanf("%d%d", &M, &N)) 44. { 45. count = 0; 46. if(M < 0 || N < 0) break; 47. for(i = 0; i < M; i++) scanf("%s", map[i]); //以行为单位为map地图赋值 48. //遍历地图、递归计数 49. for(i = 0; i < M; i++) 50. for(j = 0; j < N; j++) 51. if(map[i][j] != 'Y') { DFS(i, j); count++; } 52. printf("%d\n", count); 53. } 54. return 0; 55. }
运行结果:
如有Bug,欢迎拍砖~ :)
本文由职坐标整理并发布,了解更多内容,请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号