lightoj 1092

发表于   |   分类于   |     |   阅读次数

摘要:
一次考虑2行的状态压缩

正文:

题意：给一个最多8 8的方格，’.’代表为开，’‘代表为关，每次反转一个按钮，那么它周围的八个联通块都会翻转。问最少多少次将其变成全关，如果不可能输出-1。

按状压思路想，8联通单独处理很麻烦，我们可以预处理出一行所有翻转情况对上中下三行的影响。dp[i][s]，s高m位代表上一行的状态，s低m位表示中间这行的状态，现在翻转的是i+1行，那么这一次翻转过之后，后面的翻转对这次的高m位永远不会有影响，因此在这一次翻转，必须把其全部置为1，找一开始预处理中“上”满足异或和全部为1的翻转，然后进行转移。我用了一个队列维护状态，因为状态太多了，怕超时…然而现在突然发现好像更慢（对的，是更慢了，刚测过，以后再也不用队列写状压…）。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<utility>
#include<sstream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
int ori[20],tar[20];
int a[3][8],dp[10][70000];
int dir[9][2] = {-1,-1,-1,0,-1,1,0,-1,0,0,0,1,1,-1,1,0,1,1};
char s[20][20];
bool leap[10][70000];
struct Node{
    int first,second,st;
    Node(int first = 0,int second = 0,int st = 0) : first(first),second(second),st(st){}
};
vector<Node>vt[10][300];
void work(int x,int y,int len){
    for(int i = 0;i < 9;i++){
        int tempx = x + dir[i][0];
        int tempy = y + dir[i][1];
        if(tempx < 0 || tempx >= 3 || tempy < 0 || tempy > len)continue;
        a[tempx][tempy] ^= 1;
    }
}
void dfs(int st,int fuck,int de){
    if(st == de + 1){
        int ans1 = 0,ans2 = 0,ans3 = 0;
        for(int i = 0;i <= de;i++){
            ans1 = ans1*2 + a[0][i];
            ans2 = ans2*2 + a[1][i];
            ans3 = ans3*2 + a[2][i];
        }
        /*for(int i = 0;i < 3;i++){
            for(int j = 0;j <= de;j++)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;*/
        vt[de][ans1].push_back(Node(ans2,ans3,fuck));
        return;
    }
    dfs(st + 1,fuck,de);
    work(1,st,de);
    dfs(st + 1,fuck + 1,de);
    work(1,st,de);
}
void init(int x){
    memset(a,0,sizeof(a));
    dfs(0,0,x);
}
int main()
{
	#ifdef LOCAL
	freopen("C:\\Users\\ΡΡ\\Desktop\\in.txt","r",stdin);
	//freopen("C:\\Users\\ΡΡ\\Desktop\\out.txt","w",stdout);
	#endif // LOCAL
	for(int i = 0;i < 8;i++)
	    init(i);
    int t,kase = 1;
    scanf("%d",&t);
    while(t--){
        printf("Case %d: ",kase++);
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 0;i < n;i++)
            scanf("%s",s + i);
        memset(ori,0,sizeof(ori));
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(s[i][j] == '.')
                    ori[i] = ori[i]*2;
                else
                    ori[i] = ori[i]*2 + 1;
            }
        }
        //memset(leap,false,sizeof(leap));
        //memset(dp,0x3f,sizeof(dp));
        //queue<P>p;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < (1 << (m*2));j++)
                dp[i][j] = inf;
        for(int i = 0;i < (1 << m);i++){
            for(int j = 0;j < vt[m - 1][i].size();j++){
                int now1 = vt[m - 1][i][j].first ^ ori[0];
                int now2 = vt[m - 1][i][j].second ^ ori[1];
                int now = (now1 << m) + now2;
                /*cout<<now<<endl;
                for(int i = 2*m - 1;i >= m;i--)
                    cout<<((now >> i)&1);
                cout<<endl;
                for(int i = m - 1;i >= 0;i--)
                    cout<<((now >> i)&1);
                cout<<endl<<endl;*/
                if(dp[0][now] > vt[m - 1][i][j].st){
                    dp[0][now] = vt[m - 1][i][j].st;
                    /*if(!leap[0][now]){
                        leap[0][now] = true;
                        p.push(P(0,now));
                    }*/
                }
            }
        }
        /*while(p.size()){
            P temp = p.front();p.pop();
            if(temp.first == n - 1)continue;
            int now1 = temp.second >> m;
            int now2 = temp.second & ((1 << m) - 1);
            int tarnow = now1 ^ ((1 << m) - 1);
            for(int i = 0;i < vt[m - 1][tarnow].size();i++){
                int nxt1 = now2 ^ vt[m - 1][tarnow][i].first;
                int nxt2 = ori[temp.first + 2] ^ vt[m - 1][tarnow][i].second;
                int nxt = (nxt1 << m) + nxt2;
                if(dp[temp.first + 1][nxt] > dp[temp.first][temp.second] + vt[m - 1][tarnow][i].st){
                    dp[temp.first + 1][nxt] = dp[temp.first][temp.second] + vt[m - 1][tarnow][i].st;
                    if(!leap[temp.first + 1][nxt]){
                        leap[temp.first + 1][nxt] = true;
                        p.push(P(temp.first + 1,nxt));
                    }
                }
            }
        }*/
        for(int i = 0;i < n - 1;i++){
            for(int s = 0;s < (1 << (m*2));s++){
                if(dp[i][s] == inf)continue;
                int now1 = s >> m;
                int now2 = s & ((1 << m) - 1);
                int tarnow = now1 ^ ((1 << m) - 1);
                for(int j = 0;j < vt[m - 1][tarnow].size();j++){
                    int nxt1 = now2 ^ vt[m - 1][tarnow][j].first;
                    int nxt2 = ori[i + 2] ^ vt[m - 1][tarnow][j].second;
                    int nxt = (nxt1 << m) + nxt2;
                    dp[i + 1][nxt] = min(dp[i + 1][nxt],dp[i][s] + vt[m - 1][tarnow][j].st);
                }
            }
        }
        int ans = inf;
        int temp = ((1 << m) - 1) << m;
        for(int i = 0;i < (1 << m);i++)
            ans = min(ans,dp[n - 1][temp + i]);
        if(ans == inf)
            printf("impossible\n");
        else
            printf("%d\n",ans);
    }
	return 0;
}