题意: 给一个 r*c 的矩阵开关 (初始全打开的), 每次按下一个开关都会改变 3*3 范围内的有 * 的地方的状态, 问你最少几步能让开关全闭上, 按升序输出按哪些按钮
思路: 每个按钮至多按一下, 按按钮的顺序和结果无关. 我们把当前矩阵的开关状态状压到 long long, 并且预处理按下每个按钮的变化, 这样可以直接异或得到新的状态. 这里还需要剪枝, 因为顺序无关, 我们直接从 1 按到 r*c, 那么如果我们按到第 k 行, 现在就已经影响不到 k-2 行了, 所以 k-2 行如果有开关没闭上就 return.
代码:
- #include<set>
- #include<map>
- #include<stack>
- #include<cmath>
- #include<queue>
- #include<vector>
- #include<string>
- #include<cstdio>
- #include<cstring>
- #include<sstream>
- #include<iostream>
- #include<algorithm>
- typedef long long ll;
- using namespace std;
- const int maxn = 1e5 + 10;
- const int MOD = 1e9 + 7;
- const int INF = 0x3f3f3f3f;
- int r, c;
- char s[10][10];
- ll change[30], ansStep[30], step[30], vis[10][10], lit, ansCnt, cnt, OK;
- void init(int x, int y){
- int pos = (x - 1) * c + y;
- change[pos] = 0;
- for(int i = 1; i <= 3; i++){
- for(int j = 1; j <= 3; j++){
- if(s[i][j] == '.') continue;
- int xx = x + i - 2, yy = y + j - 2;
- if(xx <1 || xx> r || yy <1 || yy> c) continue;
- ll p = (xx - 1) * c + yy;
- change[pos] += (1LL <<p);
- }
- }
- }
- void dfs(int pos){
- if(pos> r * c) return;
- int x = pos / c, y = pos % c;
- if(x>= 3){
- for(int i = 1; i <= c; i++){
- int pos2 = (x - 3) * c + i;
- if(!(lit & (1LL << pos2))) return;
- }
- }
- lit ^= change[pos];
- vis[x][y] = 1;
- step[cnt++] = pos;
- if(lit == OK){
- if(cnt < ansCnt){
- for(int i = 0; i < cnt; i++)
- ansStep[i] = step[i];
- ansCnt = cnt;
- lit ^= change[pos];
- vis[x][y] = 0;
- cnt--;
- return;
- }
- }
- dfs(pos + 1);
- lit ^= change[pos];
- vis[x][y] = 0;
- cnt--;
- dfs(pos + 1);
- }
- int main(){
- int ca = 1;
- while(~scanf("%d%d", &r, &c) && r + c){
- OK = 0;
- for(int i = 1; i <= 3; i++) scanf("%s", s[i] + 1);
- for(int i = 1; i <= r; i++){
- for(int j = 1; j <= c; j++){
- init(i, j);
- OK += (1LL << ((i - 1) * c + j));
- }
- }
- ansCnt = 100;
- memset(vis, 0, sizeof(vis));
- dfs(1);
- printf("Case #%d\n", ca++);
- if(ansCnt == 100) printf("Impossible.\n");
- else{
- for(int i = 0; i < ansCnt; i++){
- if(i != 0) printf(" ");
- printf("%d", ansStep[i]);
- }
- printf("\n");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2961011.html