poj 1979 zoj 2165 Red and Black 深搜做法

poj 1979 zoj 2165 Red and Black 深搜做法

/*
第一个深搜
参考了大牛的代码
并作了少许优化
*/
#define LOCAL
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iomanip>
#include<string>
#include<algorithm>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#define N 25
using namespace std;
int m,n,ans,rec[N][N],dir[4][2]={0,1,0,-1,1,0,-1,0};   //控制转向
bool legal(int x,int y)                                                  //判断数据是否合法
{if(x>=1&&x<=m&&y>=1&&y<=n) return true;return false;}
void DFS(int x,int y)                       //递归搜索
{
	int i,sx,sy;
	rec[x][y]=1;ans++;//标记当前点已经遍历过,每遍历一个节点ans+1
	for(i=0;i<4;i++)                          
	{
		sx=x+dir[i][0];sy=y+dir[i][1];//转向
		if(!rec[sx][sy]&&legal(sx,sy)) //若当前结点未被遍历且”合法“遍历该节点
			 DFS(sx,sy);
	}
}
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif
 
	   int i,j,x,y;char ch;
	   while(cin>>n>>m&&m&&n)
	   {
		   memset(rec,0,sizeof(rec));
		   for(i=1;i<=m;i++)
			{
				for(j=1;j<=n;j++)
				{
					cin>>ch;
					if(ch=='#') rec[i][j]=1;
					else if(ch=='@') {x=i;y=j;}
				}
			}
		    ans=0;  
			DFS(x,y);
			cout<<ans<<endl;
	   }
	   return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注