当前位置: 代码迷 >> 综合 >> uva572--oil deposits--dfs算法
  详细解决方案

uva572--oil deposits--dfs算法

热度:52   发布时间:2023-11-06 19:31:26.0

题意:

对于给出的矩阵,求独立油田的个数。其中@代表油田,独立的意思是其上下左右以及对角线都没有油田,若有的话就视为同一个。

思路:

dfs,分别向八个方向搜索,同时进行标记,最后输出标记的个数即可。

#include<iostream>
#include<cstring>
using namespace std;
char a[105][105];
int biao[105][105]; 
int co,m,n;
void dfs(int y,int x,int id){if(y<0||x<0||y>=m||x>=n||a[y][x]!='@')return;if(biao[y][x]>0) return;biao[y][x]=id;for(int dm=-1;dm<=1;dm++)for(int dn=-1;dn<=1;dn++)if(dm!=0||dn!=0) dfs(y+dm,x+dn,id); }int main(){	while(scanf("%d %d",&m,&n)&&m&&n){memset(biao,0,sizeof(biao));co=0;for(int i=0;i<m;i++)cin>>a[i];for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(biao[i][j]==0&&a[i][j]=='@')dfs(i,j,++co);cout<<co<<endl; }return 0;}