深度搜索和广度搜索是我们搜索算法中常用的一种思想
4-1 油田合并问题
问题描述 :
大致思想:给一幅油田地图,算出油田中可以至少需要几个泵,相连的油田中的油可以相互流动
输入地图 m*n (<=50)
然后给出数据
输出泵的个数
源代码:
#include<stdio.h> #define N 50 char Map[N][N]; int Flag[N][N]; int m,n; void dfs(int i,int j) { //四个方向搜索 //判断边界 if(i<0||i>=m||j<0||j>=n)return ; Flag[i][j]=1;//遍历了 if(Flag[i-1][j]==0&&Map[i-1][j]=='@')dfs(i-1,j); if(Flag[i+1][j]==0&&Map[i+1][j]=='@')dfs(i+1,j); if(Flag[i][j-1]==0&&Map[i][j-1]=='@')dfs(i,j-1); if(Flag[i][j+1]==0&&Map[i][j+1]=='@')dfs(i,j+1); } int main() { int i,j,ans; while(scanf("%d%d",&m,&n)!=EOF) { //初始化 getchar(); for(i=0;i<m;i++) { for(j=0;j<n;j++) { Flag[i][j]=0; scanf("%c",&Map[i][j]); } getchar(); } ans=0; for(i=0;i<m;i++)3 for(j=0;j<n;j++) { if(Flag[i][j]==0&&Map[i][j]=='@') { ans++; dfs(i,j); } } printf("%d\n",ans); } return 0; }
4-2新连连看
问题描述:
许多人都玩过连连看的游戏,今天玩一个类似的游戏,在一个10*10大小的小方格组成的矩形中有n(n《10)对字符,他们是大写字母中的前n个,矩形里有些位置可以从上面走过有些则不能,能走过的位置用.来标记,不能的用#来标记,如果两个相同的字符是联通的,从一个字符能走到另一个字符,注意只能从上下左右走,某个位置有其他字符的时候是不能走通的,那么这对字符能够进行配对,如果这对字符匹配成功,则从矩形中消失,也就是说这个位置可以变的走动了
现在的问题是请你决定这些字符的配对的顺序(只有能配对的才进行配对)使得n对字符最后都配对成功
输入:
先给出一个正整数,表示有t组测试数据
每组有10行 每行有10个字符这些字符只能是. #和大写字符组成
输出:
若每组测试数据中的n对字符可以配对成功,输出配对顺序,如果有多种配对成功的顺序,请输出字典中顺序最小的那组
否则输出 MyGod
4-3八数码问题