做企业网站哪个平台好,网站后台怎么进入wordpress,河南项目备案信息网,wordpress主题08影视正题
题目链接#xff1a;https://vijos.org/p/1197 大意
有5*5个开关#xff0c;每次选择一个地方时它和它上下左右的开关都会取反#xff0c;求将所有开关都变成1的最少次数。 解题思路
首先我们知道一个位置一定不会点击超过一次。这样我们就可以得出一条性质#xf…正题
题目链接https://vijos.org/p/1197 大意
有5*5个开关每次选择一个地方时它和它上下左右的开关都会取反求将所有开关都变成1的最少次数。 解题思路
首先我们知道一个位置一定不会点击超过一次。这样我们就可以得出一条性质当第一行都已经决定是否点击过后第一行就只能由第二行点击那么这时第二行只能点击第一行还没打开的灯的下面这样以此类推的话第二条性质就出来了。 如果第一行决定是否点击的方案了如果有解的话那么只有一种点击方式。 这样的话我们就可以枚举第一行每格是否点击然后我们就可以推出后面几行如果有解的话那么就取最小解。 代码
#includecstdio
#includeiostream
#includealgorithm
using namespace std;
const int n5;
int s[7],bs[7],ans,mins,t;
char a;
int main()
{scanf(%d,t);for (int ti1;tit;ti){for(int i1;in;i){bs[i]0;for(int j1;jn;j){cina;a-0;bs[i](bs[i]1)a;//读入}}mins2147483647;for (int i0;i31;i)//枚举{ans0;for (int j1;jn;j)s[j]bs[j];for (int j0;jn;j)if (i(1j))//是否点击{if (j!n-1)s[1]^1(j1);s[1]^1j;if (j!0)s[1]^1(j-1);s[2]^1j;ans;}//改变和统计for (int j2;jn;j)for (int k0;kn;k)if (!((s[j-1]k)1))//上一行是否还有{if (k!n-1)s[j]^1(k1);s[j]^1k;if (k!0)s[j]^1(k-1);s[j1]^1k;ans;}//改变和统计if (s[n]31)//有解minsmin(mins,ans);//取最小答案}if (mins6) printf(-1\n);else printf(%d\n,mins);}
}
