1 条题解

  • 0
    @ 2025-10-8 16:55:49
    #include <bits/stdc++.h>
    using namespace std;
    bool a[5][5];
    int ans = (1 << 16) - 1;//最多有2的16次方-1的情况
    int ccc(int x)
    {
    	int cnt = 0;
    	for(int i = 1; i <= 16; i++) if (x & (1 << i - 1)) cnt++;
    	return cnt;
    }
    void f(int x)
    {
      //改变第b列和第c行的状态
    	int b = (x - 1) / 4 + 1,c = (x - 1) % 4 + 1;
    	for(int i = 1; i <= 4; i++) a[b][i] ^= 1;
    	for(int i = 1; i <= 4; i++) a[i][c] ^= 1;
    	a[b][c] ^= 1;
    }
    bool check()
    {
      //判断是否全是1
    	for(int i = 1; i <= 4; i++)
    	{
    		for(int j = 1; j <= 4; j++)
    		{
    			if (a[i][j] == 0) return 0;
    		}
    	}
    	return 1;
    }
    int main()
    {
    	for (int i = 1; i <= 4; i++)
    	{
    		for (int j = 1; j <= 4; j++)
    		{
    			char c;
    			cin >> c;
    			if (c == '+') a[i][j] = 0;//+就是0
    			else a[i][j] = 1;//-就是1
    		}
    	}
    	for (int i = 0; i < (1 << 16); i++)
    	{
    		for (int j = 1; j <= 16; j++) if (i & (1 << j - 1)) f(j); 
    		if (check() && ccc(i) < ccc(ans)) ans = i;
    		for (int j = 1; j <= 16; j++) if (i & (1 << j - 1)) f(j);
    	}
    	cout << ccc(ans) << "\n";
    	for (int i = 1; i <= 16; i++) if (ans & (1 << i - 1)) cout << (i - 1) / 4 + 1 << ' ' << (i - 1) % 4 + 1 << "\n";
    	return 0;
    }
    
    • 1

    *【穷举+状压】飞行员兄弟[POJ2965]The Pilots Brothers' refrigerator

    信息

    ID
    1153
    时间
    1000ms
    内存
    64MiB
    难度
    1
    标签
    递交数
    39
    已通过
    29
    上传者