0201 费解的开关 0x00「基本算法」例题

题目

传送门

题解

枚举第一行的状态，然后向下搜索按题意模拟即可

code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define add(x) t[x].add
#define clean(x, y) memset(x, y, sizeof(x))
const int maxn = 5e5 + 100;
const int inf = 0x3f3f3f3f;
const int dir[5][2] = { 0, 0, 1, 0, -1, 0, 0, 1, 0, -1 };
typedef long long LL;
using namespace std;

template <typename T>
inline void read(T &s) {
    s = 0;
    T w = 1, ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch))  { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w;
}

template<typename T>
inline void write(T s) {
	if (s < 0) putchar('-'), s = -s;
	if (s > 9) write(s / 10);
	putchar(s % 10 + '0');
}

int n;
int m;
int ans;
int res;
int a[7][7];
int g[7][7];
bool flag;

inline void turn(int x, int y) {
	for (int k = 0; k < 5; ++k)
	 	g[x + dir[k][0]][y + dir[k][1]] ^= 1;
}

int main() { 
	read(n);
	while (n--) {
		for (int i = 1; i <= 5; ++i) {
			for (int j = 1; j <= 5; ++j) {
				char ch;
				cin >> ch;
				a[i][j] = (int)(ch - '0');
			}
		}
		
		ans = inf;
		for (int k = 1; k <= 32; ++k) {
			for (int i = 1; i <= 5; ++i)
				for (int j = 1; j <= 5; ++j)
					g[i][j] = a[i][j];
			
			res = 0;
			
			for (int i = 0; i < 5; ++i) {
				if ((k >> i) & 1) {
					++res;
					turn(1, i + 1);
				}
			}
			
			for (int i = 2; i <= 5; ++i) {
				for (int j = 1; j <= 5; ++j) {
					if (g[i - 1][j] == 0) {
						++res;
						turn(i, j);
					}
				}
			}
			
			flag = true;
			for (int i = 1; i <= 5; ++i) {
				if (g[5][i] == 0) {
					flag = false;
					break;
				}
			}
			if (flag) 
				ans = min(ans, res);
		}
		if (ans > 6) ans = -1;
		write(ans), putchar('\n');
	}
	
	return 0;
}