首页 > 代码库 > 2014 Super Training #6 G Trim the Nails --状态压缩+BFS

2014 Super Training #6 G Trim the Nails --状态压缩+BFS

2024-07-11 01:11:01   217人阅读

原题： ZOJ 3675 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3675

由m<=20可知，可用一个二进制数表示指甲的状态，最多2^20，初始状态为0，表示指甲都没剪，然后BFS找解，每次枚举剪刀的两个方向，枚举移动的位数进行扩展状态即可。

代码:

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>using namespace std;#define N 10007struct node{    int state,step;    node(int _state,int _step)    {        state = _state;        step = _step;    }    node(){}};int vis[1<<21];int cut[2]; //两个方向queue<node> que;int n,m;int bfs(int s){    int i,j,k;    memset(vis,0,sizeof(vis));    while(!que.empty())        que.pop();    int E = (1<<m)-1;    que.push(node(s,0));    vis[s] = 1;    while(!que.empty())    {        node tmp = que.front();        que.pop();        int state = tmp.state;        int step = tmp.step;        int tms = state;        for(i=0;i<2;i++) //direction        {            for(j=0;j<n;j++)  //move            {                int end = ((cut[i]>>j) | tms) & E;  // &E : keep m bit                if(vis[end])                    continue;                vis[end] = 1;                if(end == E)                    return step+1;                que.push(node(end,step+1));            }            for(j=0;j<m;j++)            {                int to = ((cut[i]<<j) | tms) & E;                if(vis[to])                    continue;                vis[to] = 1;                if(to == E)                    return step+1;                que.push(node(to,step+1));            }        }    }    return -1;}int main(){    int i,j;    char ss[13];    while(scanf("%d",&n)!=EOF)    {        cut[0] = cut[1] = 0;        scanf("%s",ss);        for(i=0;i<=n;i++)        {            if(ss[i] == ‘*‘)            {                cut[0] |= (1<<i);                cut[1] |= (1<<(n-1-i));            }        }        scanf("%d",&m);        if(cut[0] == 0)        {            puts("-1");            continue;        }        printf("%d\n",bfs(0));    }    return 0;}
View Code

 


联系
我们