Posted on 2010-08-27 04:36
acronix 阅读(135)
评论(0) 编辑 收藏 引用 所属分类:
qqy解题报告
//考察点: 简单dfs
//思路: 这个题目可以用dfs做也可用bfs做 但是bfs还没有想到怎么做. 在dfs的过程中就能顺便计算出周长(perimeter) 像类似这样的题目非常像走迷宫类型. 因为需要求解的是最终的周长 发现一个性质 如果某个X跟其他的X相邻的话,相邻处就要扣掉一条边(初始perimeter is 4) 于是利用深搜找到所有的可能.
//提交情况 3WA 2AC
WA 因为 技术变量 i,j 位置没有放对 最好不要开成全局的 否则会出现莫名其妙的错误.
//收获: 第一次接触dfs. 知道dfs是利用递归的思路来做的 只要子问题跟原问题的性质相同 递归就能发挥作用.
//经验: 写递归程序的时候可以把之后的问题看成是子问题 于是处理好程序出口以后就可以直接调用自己了.
//AC code
#include<stdio.h>
#include<memory.h>
#define maxn 21
char a[maxn][maxn];
bool c[maxn][maxn];
int e[8][2]={{-1,1},{0,1},{1,1},{-1,0},{1,0},{-1,-1},{0,-1},{1,-1}};
int f[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int sum;
int n,m,p,q;
void dfs(int p1,int q1)
{
int i,j;
for(i=0;i<8;i++)
{
int pp = p1 + e[i][0];
int qq = q1 + e[i][1];
if(pp<0||pp>=n||qq<0||qq>=m) continue;
if(a[pp][qq] == '.') continue;
if(c[pp][qq] == 1) continue;
for(j=0;j<4;j++)
{
int x = pp + f[j][0];
int y = qq + f[j][1];
if(x<0||x>=n||y<0||y>=m) {sum++;continue;}
if(c[x][y] == true)
{
sum--;
continue;
}
else
{
sum++;
continue;
}
}
c[pp][qq] = true;
dfs(pp,qq);
}
}
int main()
{
int i;
//freopen("pku_1111_in.txt","r",stdin);
while(1)
{
scanf("%d%d%d%d",&n,&m,&p,&q);
if(n+m+p+q == 0) break;
for(i=0;i<n;i++)
scanf("%s",a[i]);
p-=1,q-=1;
if(a[p][q] == '.') {printf("0\n");continue;}
memset(c,0,sizeof(c));
sum = 4;
c[p][q] = true;
dfs(p,q);
printf("%d\n",sum);
}
return 0;
}