posts - 64, comments - 4, trackbacks - 0, articles - 0

pku_1111

Posted on 2010-08-27 04:36 acronix 阅读(132) 评论(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] == 1continue;
        
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+== 0break;
        
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;
}


 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理