admin管理员组文章数量:1648695
题目链接:Oil Deposit
这个题一看就是要用深搜(dfs)啦
找到一个符合条件(1.不越界2.有油田)的位置时,那么我们对它进行以下操作:
1.将此位置标记为访问过(此题中即将@改为*)
2.对此位置的周围位置进行探索(由于包括斜对角,所以有8个方位)
3.当探索到一个符合条件(上述条件)的位置时,又重复1,2操作。
那么dfs函数的写法就是这样:
void dfs(int x,int y)
{
int i,j,dx,dy;
a[x][y]='*';
for( i=0;i<8;i++){
dx=x+b[i][0];
dy=y+b[i][1];
if(1<=dx&&dx<=m&&1<=dy&&dy<=n&&a[dx][dy]=='@')
dfs(dx,dy);
}
return ;
}
用一个5x5的地图来举例(0代表无油,1代表有)
0 0 0 0 1
0 1 1 0 1
0 1 0 0 1
1 1 1 0 1
1 1 0 0 1
我们走到第一行第五列时发现符合条件的,那么我们对他进行操作,于是走到第二行第五列再进行操作,于是第三行第五列。。。最后第五行第五列后找不到就层层返回。
变成了:
0 0 0 0 0
0 1 1 0 0
0 1 0 0 0
1 1 1 0 0
1 1 0 0 0
又走到了第二行第二列进行操作,根据我的顺序(从右开始顺时针探索)先找到第二行第三列,在第二行第三列的探索中找到第三行第二列,再依次探索。
代码实现
#include<stdio.h>
int m,n;
char a[105][105];
int b[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
void dfs(int x,int y)
{
int i,j,dx,dy;
a[x][y]='*';
for( i=0;i<8;i++){
dx=x+b[i][0];
dy=y+b[i][1];
if(1<=dx&&dx<=m&&1<=dy&&dy<=n&&a[dx][dy]=='@')
dfs(dx,dy);
}
return ;
}
int main()
{
int i,j,count=0;
while(scanf("%d %d",&m,&n)!=EOF&&m!=0)
{
getchar();
count=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
scanf("%c",&a[i][j]);
}
getchar();
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]=='@'){
dfs(i,j);
count++;
}
}
}
printf("%d\n",count);
}
return 0;
}
版权声明:本文标题:Oil Deposit深搜问题 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729493577a1202684.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论