UVA-10318 Security Panel （DFS+剪枝）

题目大意：求将一个r*c的按钮矩阵由全部为关变成全部为开的最少按扭次数，每按一次开关能作用到的范围不定。

题目分析：开关问题。打眼一看就是BFS+位压缩，但是写出来之后TLE。用DFS不断更新最优解。最坏有2^25种情况，加两个剪枝：

　　一、每一个开关最多只能影响三行，当第now_r-2行仍然有开关关着，则这种方案不可能使所有按钮全部打开，剪掉（并且是主剪）；

　　二、当当前总的按按钮次数大于已经达到的答案，则剪掉；

第二个剪枝效果不强，加不加都是26ms过，但不加第一个剪枝一定TLE。

这道题用BFS的话，上面两个剪枝起不到作用。

代码如下：

# include<iostream>
# include<cstdio>
# include<queue>
# include<map>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std;
struct XY
{
    int x,y;
    XY(int _x,int _y):x(_x),y(_y){}
};
char pos[3][3];
int cnt,r,c,mark[26];
bool flag;
vector<XY>d;
map<int,char>mp;
string ans;
void init()
{
    d.clear();
    for(int i=0;i<3;++i){
        for(int j=0;j<3;++j){
            if(pos[i][j]=='*')
                d.push_back(XY(i-1,j-1));
        }
    }
}
bool ok()
{
    for(int i=1;i<=r*c;++i)
        if(mark[i]%2==0)
            return false;
    return true;
}
bool still_unlit(int row)
{
    for(int i=(row-1)*c+1;i<=row*c;++i)
        if(mark[i]%2==0)
            return true;
    return false;
}
int get_row(int n)
{
    return (n%c)?(n/c)+1:(n/c);
}
void dfs(int id,string have)
{
    if(ok()){
        if(!flag){
            flag=true;
            ans=have;
        }
        else{
            if(ans.size()>have.size())
                ans=have;
        }
        return ;
    }
    if(id>c*2&&still_unlit(get_row(id-c*2)))
        return ;
    if(flag&&have.size()>ans.size())
        return ;
    for(int i=id+1;i<=r*c;++i){
        int x=get_row(i),y=(i%c)?(i%c):c;
        for(int j=0;j<d.size();++j){
            int nx=x+d[j].x,ny=y+d[j].y,nid=(nx-1)*c+ny;
            if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&nid>=1&&nid<=r*c)
                ++mark[nid];
        }
        dfs(i,have+mp[i]);
        for(int j=0;j<d.size();++j){
            int nx=x+d[j].x,ny=y+d[j].y,nid=(nx-1)*c+ny;
            if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&nid>=1&&nid<=r*c)
                --mark[nid];
        }
    }
}
int main()
{
    for(int i=1;i<=26;++i)
        mp[i]=i+'A'-1;
    int cas=0;
    while(scanf("%d%d",&r,&c)&&r+c)
    {
        for(int i=0;i<3;++i)
            scanf("%s",pos[i]);
        printf("Case #%d
",++cas);
        init();
        memset(mark,0,sizeof(mark));
        flag=false;
        dfs(0,"");
        if(flag){
            for(int i=0;i<ans.size();++i)
                printf("%d%c",ans[i]-'A'+1,(i==ans.size()-1)?'
':' ');
        }else
            printf("Impossible.
");
    }
    return 0;
}

UVA-10318 Security Panel （DFS+剪枝）

相关推荐