学步园

DFS的两种实现：

import java.util.Scanner;

public class hdu1312DFS {

	static char map[][]=new char[22][22];
	static int x,y;
	static int inc[][]={{1,0},{0,1},{-1,0},{0,-1}};
	static int ans;
	static void init()
	{
		Scanner in=new Scanner(System.in);
		while(true)
		{
			y=in.nextInt();
			x=in.nextInt();
			if(x==0&&y==0)
				break;
			int a=-1,b=-1;
			for(int i=1;i<=x;i++)
			{
				String data=in.next();
				for(int j=1;j<=y;j++)
				{
					map[i][j]=data.charAt(j-1);
					if(map[i][j]=='@')
					{
						a=i;
						b=j;
					}
				}
			}
			ans=0;
			DFS1(a,b);
			System.out.println(ans);
		}
		
	}
	
	static void DFS(int a,int b)
	{
		if(map[a][b]=='#'||a<1||b<1||a>x||b>y)
			return;
		if(map[a][b]=='.')
		{
			ans++;
			map[a][b]='#';
		}
		
		for(int i=0;i<4;i++)
		{
			int x=a+inc[i][0];
			int y=b+inc[i][1];
			DFS(x,y);
			
		}
	}
	
	static void DFS1(int a,int b)
	{
		if(map[a][b]=='#'||a<1||b<1||a>x||b>y)
			return;
		else
		{
			ans++;
			map[a][b]='#';
			DFS1(a+1,b);
			DFS1(a,b+1);
			DFS1(a-1,b);
			DFS1(a,b-1);
		}
	}
	
	
	public static void main(String[] args) {
		init();
	}
}

BFS的实现：

import java.util.ArrayList;
import java.util.Scanner;

//BFS实现
public class hdu1312BFS {

	static int inc[][]={{1,0},{0,1},{-1,0},{0,-1}};
	static char map[][]=new char[110][110];
	static int x,y;
	class Node
	{
		int x;
		int y;
		
	}
	static int ans;
	void build()
	{
		Scanner in=new Scanner(System.in);
		while(true)
		{
			y=in.nextInt();
			x=in.nextInt();
			if(x==0&&y==0)
				break;
			int a=-1,b=-1;
			ans=1;
			for(int i=1;i<=x;i++)
			{
				String line=in.next();
				for(int j=1;j<=y;j++)
				{
					map[i][j]=line.charAt(j-1);
					if(map[i][j]=='@')
					{
						a=i;
						b=j;
					}
				}
			}
			BFS(a,b);
			
		}
	}
	 void BFS(int a,int b)
	{
		ArrayList<Node> q=new ArrayList<Node>() ;
		Node cur=new Node();
		Node next;
		cur.x=a;
		cur.y=b;
		map[a][b]='#';
		q.add(cur);
		while(!q.isEmpty())
		{
			cur=q.get(0);
			for(int i=0;i<4;i++)
			{
				next=new Node();
				next.x=cur.x+inc[i][0];
				next.y=cur.y+inc[i][1];
				if(next.y<=y&&next.x<=x&&next.x>=1&&next.y>=1&&map[next.x][next.y]=='.')
				{
					ans++;
					map[next.x][next.y]='#';
					q.add(next);
				}
				
			}
			q.remove(cur);
		}
		System.out.println(ans);
		
	}
	
	public static void main(String[] args) {
		new hdu1312BFS().build();
	}
}

再贴一个cpp的：

//============================================================================
// Name        : hdu1312BFS.cpp
// Author      : xinge
// Version     :
// Copyright   : Your copyright notice
// Description : Ansi-style
//============================================================================

#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include<cmath>
#include<queue>
using namespace std;
//BFS

char map[110][110];
int xx,yy,ans;
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
struct Node
{
	int x,y;
};

void BFS(int a,int b)
{
	queue<Node> q;
	Node cur,next;
	cur.x=a;
	cur.y=b;
	q.push(cur);
	map[a][b]='#';
	while(!q.empty())
	{
			cur=q.front();
			q.pop();
		for(int i=0;i<4;i++)
		{
			next.x=cur.x+dir[i][0];
			next.y=cur.y+dir[i][1];
			if(next.x<xx&&next.y<yy&&next.x>=0&&next.y>=0&&map[next.x][next.y]=='.')
			{
				ans++;
				map[next.x][next.y]='#';
				q.push(next);
			}
		}

	}
	printf("%d\n",ans);
}

int main() {
	while(~scanf("%d%d",&yy,&xx))
		{
			if(xx==0&&yy==0)
				break;
			int i,j,a=-1,b=-1;
			ans=1;
			for(i=0;i<xx;i++)
				scanf("%s",&map[i]);
			for(i=0;i<xx;i++)
				for(j=0;j<yy;j++)
				{
					if(map[i][j]=='@')
					{
						a=i;
						b=j;
						BFS(a,b);
					}
				}
		}
	return 0;
}