Vijos.1197 费解的开关

10111
01101
10111
10000
11011

01111
11101
10111
10000
11011

01111
11001
11001
10100
11011

3

00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

3
2
-1

解法

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

int map[1 << 25];

void bfs();
int press(int status, int num);
int main() {
memset(map, -1, sizeof(map));
bfs();

int n = 0;
scanf("%d", &n);

while(n--) {
int light = 0;
char line[10];

for(int i = 0; i < 5; i++) {
scanf("%s", line);

for(int j = 0; j < 5; j++) {
light <<= 1;
light |= (line[j] - '0');
}
}

printf("%d\n", map[light]);
}

return 0;
}

int press(int status, int num) {
int pre = status;

status ^= (1 << num);
if(num % 5 != 0) status ^= (1 << (num - 1));
if(num % 5 != 4) status ^= (1 << (num + 1));
if(num / 5 != 0) status ^= (1 << (num - 5));
if(num / 5 != 4) status ^= (1 << (num + 5));

if(pre == status || map[status] != -1)
return -1;
else if(map[status] == -1) {
map[status] = map[pre] + 1;
return status;
}
}

void bfs() {
queue<int> q;

int status = (1 << 25) - 1;
map[status] = 0;

q.push(status);

while(!q.empty()) {
status = q.front();
q.pop();

if(map[status] < 6) {
for(int i = 0; i < 25; i++) {
int now = press(status, i);

if(now != -1) q.push(tmp);
}
}
}
}


优化

详细思路

1. 每个位置至多只会被点击一次
2. 如果固定了第一行的点击方案，则整个矩阵的点击方案也都会被确定

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

int press(int status, int n);
int main() {
int n = 0;
scanf("%d", &n);

while(n--) {
int status = 0;

char tmp[10];
for(int i = 0; i < 5; i++) {
scanf("%s", tmp);

for(int j = 0; j < 5; j++) {
status <<= 1;

if(tmp[j] == '1') status |= 1;
}
}

int mintime = INF;
for(int i = 0; i < (1 << 5); i++) {
int t = i, p = status, num = 0;

for(int j = 0; j < 5; j++) {
if(((t >> (4 - j)) & 1) == 1) {
p = press(p, 24 - j);
num++;
}
}

for(int j = 1; j < 5; j++) {
for(int k = 0; k < 5; k++) {
if(((p >> (24 - 5 * j + 5 - k)) & 1) == 0) {
p = press(p, 24 - 5 * j - k);
num++;
}
}
}

bool flag = true;
for(int j = 0; j < 5; j++) {
if((p & 1) == 0) {
flag = false;
break;
}

p >>= 1;
}

if(flag) {
mintime = min(mintime, num);
}
}

printf("%d\n", mintime > 6 ? -1 : mintime);
}

return 0;
}

int press(int status, int n) {
status ^= (1 << n);
if(n / 5 != 4) status ^= (1 << (n + 5));
if(n / 5 != 0) status ^= (1 << (n - 5));
if(n % 5 != 4) status ^= (1 << (n + 1));
if(n % 5 != 0) status ^= (1 << (n - 1));
return status;
}