以前做过POJ上的3620,题意大概是要你求出相邻的X有多少个,而这个题呢,则是要求你求出整个互相邻接的X所够成的周长;
我个人认为,这两道题有异曲同工之妙。
这道题和3620不同的是,我们不能将所有与X相邻的结点都压栈,而是选择X结点压栈,为什么呢?我想了想,因为此题的周长是在你考察X的基础上向四面八方试探而求出的。你最好是立足与X结点,由于对压栈元素进行了限制,那么在进入dfs递归的时候也就不用大费周章的去判断
if(visit[i][j]==0)了,因为压栈的元素必须是没有考察过的X结点;当然这只不过是基于自己的个人习惯而已,我想,即使你不判断压栈元素,应该也能做出来吧,只不过这样似乎并不符合我们的思维习惯而已;
另外做这个题目的时候还遇到了一个小问题,就是cin.ignore()的使用,再输入r,c,x,y的值之后,由于回车符不可能被整型变量吃掉,所以它会滞留在缓冲区,使得在输入字符时回车符优先进入map数组,而且每一行之后都有一个回车符,所以这个cin.ignore()的位置也是不能改变的。
当让还有个有意思的地方,就是这个题要用向量来存储考察的方向,这样的话一个循环就可以考察完所有的方向,不用费力把所有的方向都写一遍了,这是一个很不错的方法,宜借鉴之;
最后要感谢一下网路上分享代码的大牛们,正是由于参考了你们的代码才使我有所进步;
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAX 100
char map[MAX][MAX];
int visit[MAX][MAX];
int sum;
int r,c;
int path[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
void dfs(int a,int b)
{
visit[a][b]=1;
int i;
for(i=0;i<8;i++)
{
int x=a+path[i][0];
int y=b+path[i][1];
if(x>=1&&x<=r&&y>=1&&y<=c)
{
if(map[x][y]=='X'&&visit[x][y]==0)
dfs(x,y);
else if(map[x][y]=='.'&&(x==a||y==b))
{
sum++;
}
}
else if(x==a||y==b)
sum++;
}
}
int main ()
{
int x,y;
int i,j;
while(scanf("%d%d%d%d",&r,&c,&x,&y))
{
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
visit[i][j]=0;
}
for(i=1;i<=r;i++)
{
cin.ignore();
for(j=1;j<=c;j++)
{
scanf("%c",&map[i][j]);
}
}
sum=0;
if(r==0&&c==0&&x==0&&y==0)
break;
dfs(x,y);
printf("%d\n",sum);
}
return 0;
}