HDU1241 Oil Deposits(油田) 深搜dfs

HDU1241：Oil Deposits
深度优先搜索dfs：

题意："@“代表石油井,”*"代表没油,如果@在八个方向有相邻,则认为同属于一个油田,输入n行m列的图,问有多少块油田?输入以0 0结束

题目和 (POJ)-2386-Lake Counting (湖计数)一样属于求连通块

代码：

import java.util.Scanner;

public class Main {
	static int N, M;// 地图长宽
	static String[] s;//地图
	static int[][] vis;//用来染色
	static int count;
// static int dir[][] = { {0,1},{0,-1},{1,0},{-1,0},{-1,-1},{1,-1},{-1,1},{1,1} };// 方向

	 static void dfs(int i, int j) {
		if (i < 0 || j < 0 || i >= N  || j >= M ||vis[i][j]==1)
			return;// 越界
		else if (s[i].charAt(j) == '*')
			return;// 障碍物
		else {
			vis[i][j]= 1;// 染色
			dfs(i - 1, j);
			dfs(i - 1, j + 1);
			dfs(i - 1, j - 1);
			dfs(i + 1, j);
			dfs(i + 1, j + 1);
			dfs(i + 1, j - 1);
			dfs(i, j + 1);
			dfs(i, j - 1);
// for(int k=0;i<8;k++){
// dfs(i+dir[k][0],j+dir[k][1]);
// }
		}
		return;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		while (in.hasNext()) {

			N = in.nextInt();
			M = in.nextInt();
			s =new String[N];//行
			vis =new int [N][M];
			count=0;
			if (N == 0 && M == 0)	break;
			for (int i = 0; i < N; i++) {
				s[i] = in.next();
			}
// Arrays.fill(vis, 0);
			for(int i=0;i<N;i++)
			{
				for(int j=0;j<M;j++)
				{
					if(s[i].charAt(j) == '@' && vis[i][j]==0){
						count++;
						dfs(i,j);
					}
				}
			}		
			System.out.println(count);
		}
	}
}

C++版：

#include<iostream>

using namespace std;

int N,M;//mapp长宽 

char mapp[105][105];

int nextt[8][2]={//方向 
					{ 0, 1}
,					{ 1, 1}
,					{ 1, 0}
,					{ 1,-1}
,					{ 0,-1}
,					{-1,-1}
,					{-1, 0}
,					{-1, 1}
,								};

void dfs(int x,int y)
{

	 for(int i=0;i<8;i++)
	 {
	 	int gx=x+nextt[i][0];
		int gy=y+nextt[i][1];	
	 	if(gx>=0 && gx<N && gy>=0 && gy<M && mapp[gx][gy]=='@' )
	 	{
	 		mapp[gx][gy]='*';
	 		dfs(gx,gy);
	 	}
	 }
}
 
int main()
{
	while(~scanf("%d%d",&N,&M) && N||M)
	{	
	    int count=0;
		for(int i=0;i<N;i++)
		{//输入数组mapp 
			for(int j=0;j<M;j++)
			{
				cin>>mapp[i][j];
			}
		}
		
	    for(int i=0;i<N;i++)
	    {
	    	for(int j=0;j<M;j++)
	    	{
	    		if(mapp[i][j]=='@')
	    		{
	    			count++;
	    			dfs(i,j);
	    		}
	    	}
	    }
	    cout<<count<<endl;
	}
	return 0;
}