分类存档：默认分类

【题目大意】

如果把P视作不能去的区域，哪个人不能通过上下左右走到达牢房边缘的话，直接就变成Ghost

然后在剩下的人里，找最大的上下左右对角线连通的连通块。

【算法分析】

一开始处理Ghost的话，从牢房边缘bfs进来，如果不能到达某个P，他就死了。

然后剩下的就是种子染色法了。

【CODE】

#include #include int m,n,lx[1111111],ly[1111111],ans,head,tail;
char map[1111][1111];
bool v[1111][1111];

inline void expand1(int tx,int ty){
    if (tx<1 || tx>m || ty<1 || ty>n || v[tx][ty]) return;
    v[tx][ty]=true;
    tail++;
    lx[tail]=tx;
    ly[tail]=ty;
}   

void getghost(){
    head=0; tail=0;
    for (int i=1;i<=m;i++){
        tail++;
        lx[tail]=i;
        ly[tail]=0;
        tail++;
        lx[tail]=i;
        ly[tail]=n+1;
    }   
    for (int i=1;i<=n;i++){
        tail++;
        lx[tail]=0;
        ly[tail]=i;
        tail++;
        lx[tail]=m+1;
        ly[tail]=i;
    }
    while (head        head++;
        if (map[lx[head]][ly[head]]==’P’ && lx[head]>0 && lx[head]<=m && ly[head]>0 && ly[head]<=n)
          continue;
        expand1(lx[head]-1,ly[head]);
        expand1(lx[head]+1,ly[head]);
        expand1(lx[head],ly[head]-1);
        expand1(lx[head],ly[head]+1);
    }   
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        if (map[i][j]==’P’ && !v[i][j])
          map[i][j]=’G’;
}

inline void expand(int tx,int ty){
    if (tx<1 || tx>m || ty<1 || ty>n || v[tx][ty] || map[tx][ty]!='P') return;
    v[tx][ty]=true;
    tail++;
    lx[tail]=tx;
    ly[tail]=ty;
}   

void bfs(int sx,int sy){
    head=0,tail=1;
    lx[1]=sx; ly[1]=sy;
    v[sx][sy]=true;
    while (head        head++;
        expand(lx[head]-1,ly[head]);
        expand(lx[head]+1,ly[head]);
        expand(lx[head],ly[head]-1);
        expand(lx[head],ly[head]+1);
        expand(lx[head]-1,ly[head]-1);
        expand(lx[head]-1,ly[head]+1);
        expand(lx[head]+1,ly[head]-1);
        expand(lx[head]+1,ly[head]+1);
    }   
    if (tail>ans) ans=tail;
}   

void solve(){
    memset(map,’P’,sizeof(map));
    memset(v,false,sizeof(v));
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        for (map[i][j]=getchar();map[i][j]==’ ‘ || map[i][j]==’n’;map[i][j]=getchar());
    getghost();
    memset(v,false,sizeof(v));
    ans=0;
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        if (map[i][j]==’P’ && !v[i][j])
          bfs(i,j);
    printf("%dn",ans);
}   

int main(){
    while (scanf("%d%d",&m,&n)!=EOF) solve();
    return 0;   
}   

【题目大意】

给出13张牌（1~9）,问摸到什么牌能赢。把所有方案在同一行输出。

【算法分析】

暴力DFS，其实有更好的复杂度为O(9*9)的方法，GDKOI上有原题。。。

但是这题规模太小了，直接暴力

【CODE】

#include #include #include #include using namespace std;

int a[20],h[20],num;
bool flag;

void dfs(int i){
    if (flag) return;
    if (num==0){
        flag=true;
        return;
    }   
    while (h[i]==0) i++;
    if (h[i]>=3){
        h[i]-=3;
        num-=3;
        dfs(i);
        h[i]+=3;
        num+=3;
    }   
    if (h[i] && h[i+1] && h[i+2]){
        h[i]–; h[i+1]–; h[i+2]–;
        num-=3;
        dfs(i);
        num+=3;
        h[i]++; h[i+1]++; h[i+2]++;
    }   
}   

bool tryit(){
    flag=false;
    num=12;
    dfs(1);
    return flag;
}   

bool solve(){
    memset(h,0,sizeof(h));
    for (int i=1;i<=14;i++){
        h[a[i]]++;
      }   
    for (int i=1;i<=9;i++)
      if (h[i]>4) return false;
    for (int i=1;i<=9;i++)
      if (h[i]>=2){
          h[i]-=2;
          if (tryit()) return true;
          h[i]+=2;
      }   
    return false;
}   

int main(){
    for (;;){
        if (scanf("%d",&a[1])==EOF) break;
        for (int i=2;i<=13;i++) scanf("%d",&a[i]);
        bool st=false;
        for (int i=1;i<=9;i++){
            a[14]=i;
            if (solve()){
                if (st) printf(" ");
                printf("%d",i);
                st=true;
            }   
        }   
        printf("n");
    }   
}