注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1547 Bubble Shooter  

2013-09-04 22:34:15|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1547
n行气球,奇数行有m个,偶数行有m-1个(偶数行的气球插在奇数行相邻两个气球之间)。a到z之间某个字母表示气球的某一种颜色,‘E’表示空。连续三个及以上的气球能够消失,悬空的气球也能消失,也就是没有和其它球相连的气球能消失。现在给出一个气球的起点,问最多有多少球能够消失。
bfs,因为偶数行的气球是在奇数行相邻两个气球之间,所以搜索的时候得按奇数行偶数行分类。把起点能搜到的点并且颜色相同的气球都赋为空;然后看第一行,能被第一行气球搜到的都不是悬空的气球,总数减去能被搜到的气球即为消失气球数。
*刚开始做的时候,计算悬空气球部分想错了,后来找到反例才发现。。。计算这部分气球还得bfs

/*
* pro.cpp
*
* Created on: 2013-09-04
* Author: fudq
*/
#include <functional>
#include <algorithm>
#include <iostream>
//#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=110;
const int M=150010;
const int MOD=20100501;
const int INF=0x7fffffff;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
//const int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,1},{1,-1},{-1,-1},{1,1}};
const double eps=1e-7;
const double PI=acos(-1.0);

inline int sign(double x){return (x>eps)-(x<-eps);}
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
/*************************/

const int dir1[6][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,-1}};//ou
const int dir2[6][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,1},{1,1}};//ji

char temp,a[N],f[N][N];
int n,m,h,w;
struct Node{
int x,y;
}v[N*N];

int bfs(int h1,int w1,int sign)
{
int tot=1;
char temp=f[h1][w1];
queue<Node>Q;
Node p,q;
p.x=h1;p.y=w1;
Q.push(p);
f[h1][w1]='E';v[0]=p;
while(!Q.empty())
{
p=Q.front();
Q.pop();
for(int i=0;i<6;i++)
{
if(p.x%2 == 0)
{
q.x=p.x+dir1[i][0];
q.y=p.y+dir1[i][1];
}
else
{
q.x=p.x+dir2[i][0];
q.y=p.y+dir2[i][1];
}
if(q.x>=0 && q.x <n && q.y>=0 && q.y<(m-q.x%2) && f[q.x][q.y]!='E')
{
if(sign && f[q.x][q.y] != temp)
continue;
f[q.x][q.y]='E';
v[tot++]=q;
Q.push(q);
}
}
}
if(sign && tot < 3)
{
for(int i=0;i<tot;i++)
f[v[i].x][v[i].y]=temp;
}
return tot;
}

void solve()
{
h--;w--;
int s=0,ans=0;
for(int i=0;i<n;i++)
{
scanf("%s",f[i]);
for(int j=0;j<m-i%2;j++)
if(f[i][j]<='z' && f[i][j]>='a')
s++;
}
bfs(h,w,1);
for(int i=0;i<m;i++)
if(f[0][i] != 'E')
ans+=bfs(0,i,0);
printf("%d\n",s-ans);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
while(scanf("%d%d%d%d",&n,&m,&h,&w)!=EOF)
solve();
return 0;
}



  评论这张
 
阅读(95)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017