题解 P2741 【[USACO4.4]重叠的图像Frame Up】

Bzy_temp · 2017-10-13 13:43:41 · 题解

没有用到拓扑排序（也不会用）,bfsAC没报时间，只是代码有点长

#include<bits/stdc++.h>//万能头文件 
using namespace std;//流操作命名空间 
char mp[35][35];//地图 
bool lt[30],gt[30],ud[30];
//lt出现字母//gt该字母是否已近可以解锁//ud该字母是否已经被解锁 
int edge[30][4];//每个字母框的四个边 
int a,b;//长宽 
string ans[10000];int pt=0;//答案+指针//排序输出 
//结构体//bfs时传递状态 
struct node{
    char  mp[35][35];
    bool  gt[30];
    bool  ud[30];//同上 
    char used[30];//记录过去解锁的字母 
    int point;
    node(){
        memset(mp,' ',sizeof(mp  ));
        memset(gt, 0 ,sizeof(gt  ));
        memset(ud, 0 ,sizeof(ud  ));
        memset(used,0,sizeof(used));
        point=0;//构造函数 
    }
};
queue<node>que;//队列bfs用 
//判断该状态是否可以输出，及是否全部解锁 
bool checkout(node nod){
    for(int i=0;i<=25;i++)if(lt[i] xor nod.ud[i])return false;
    return true;
}
//搜索这个字母是否可以解锁 
bool search(node nod,int index){
    for(int i=edge[index][0];i<=edge[index][1];i++){
        int now1=nod.mp[i][edge[index][2]];
        int now2=nod.mp[i][edge[index][3]];
        if(now1!=(char)(index+65) and now1!='*')return false;
        if(now2!=(char)(index+65) and now2!='*')return false;
    }
    for(int i=edge[index][2];i<=edge[index][3];i++){
        int now1=nod.mp[edge[index][0]][i];
        int now2=nod.mp[edge[index][1]][i];
        if(now1!=(char)(index+65) and now1!='*')return false;
        if(now2!=(char)(index+65) and now2!='*')return false;
    }
    return true;
}
//解锁这个字母 
node reclear(node nod,int index){
    for(int i=edge[index][0];i<=edge[index][1];i++){
        nod.mp[i][edge[index][2]]='*';
        nod.mp[i][edge[index][3]]='*';
    }
    for(int i=edge[index][2];i<=edge[index][3];i++){
        nod.mp[edge[index][0]][i]='*';
        nod.mp[edge[index][1]][i]='*';
    }
    return nod;
}
//初始化，寻找lt与edge 
void init(node nod){
    for(int i=0;i<=a-1;i++)for(int j=0;j<=b-1;j++){
        int now=nod.mp[i][j]-65;        if(now>=0 and now<=25){
            if(lt[now])edge[now][1]=i;
            else       edge[now][0]=i,lt[now]=true;
        }
    }
    for(int i=0;i<=29;i++)lt[i]=false;
    for(int i=0;i<=b-1;i++)for(int j=0;j<=a-1;j++){
        int now=nod.mp[j][i]-65;
        if(now>=0 and now<=25){
            if(lt[now])edge[now][3]=i;
            else       edge[now][2]=i,lt[now]=true;
        }
    }
}
//主函数//bfs 
int main(){
    cin>>a>>b;
    node all=*new node();
    for(int i=0;i<=a-1;i++)cin>>all.mp[i];//输入 
    init(all);que.push(all);//初始化 
    //bfs 
    while(!que.empty()){
        node now=que.front();que.pop();
        if(checkout(now)){
            //如果全部解锁成功,记录used 
            for(int i=now.point-1;i>=0;i--)ans[pt]+=now.used[i];
            pt++;
            continue;
        }
        for(int i=0;i<=25;i++)if(lt[i] xor now.gt[i]){
            //若果还没解锁，就搜索是否可以解锁 
            if(search(now,i))now.gt[i]=true;
        }
        for(int i=25;i>=0;i--)if(now.gt[i] xor now.ud[i]){
            //解锁所有可以解锁的//传递状态 
            node next=now;
            next.ud[i]=true;
            next=reclear(next,i);
            next.used[next.point++]=(char)(i+65);
            que.push(next);
        }
    }
    sort(ans,ans+pt);//排序输出 
    for(int i=0;i<=pt-1;i++)cout<<ans[i]<<"\n";
    return 0;
}