> /*
> 
> 参考高手的高效解法：
> *********************************
> 此上证其可以按以上步骤使数组中值都为‘-’
> ********************************
> 在上述证明中将所有的行和列的位置都加1后，在将其模2之前,对给定的数组状态，将所有的位置操作其所存的操作数个次数，举例，如果a[i][j]==n,则对（i,j）操作n次，当所有的操作完后，即全为‘-’的数组。
> 其实就是不模2的操作，作了许多的无用功。
> 以上的操作次序对结果无影响，如果存在一个最小的步骤，则此步骤一定在以上操作之中。（简单说下：因为以上操作已经包含了所有可改变欲改变位置的操作了）
> 而模2后的操作是去掉了所有无用功之后的操作，此操作同样包含最小步骤。
> 但模2后的操作去掉任何一个或几个步骤后，都不可能再得到全为‘-’的。（此同样可证明：因为操作次序无影响，先进行最小步骤，得到全为‘-’，如果还剩下m步，则在全为‘-’的数组状态下进行这m步操作后还得到一个全为
> ‘-’的数组状态，此只能是在同一个位置进行偶数次操作，与前文模2后矛盾，所以m=0），因此模2后的操作即为最小步骤的操作。
> */
> #include <iostream>
> using namespace std;
> 
> bool mark[4][4];
> char s[4][4];
> 
> int main()
> {
>     int i,j,k;
>     int ci[16],cj[16];
>     int nas = 0;
>     memset(mark,0,sizeof(mark));
> 	for(i = 0;i < 4;i++)
> 		cin >> s[i];
>     for(i = 0;i < 4;i++)
>         for(j = 0;j < 4;j++)
>         {
>             char c = s[i][j];
>             if(c == '+')
>             {
>                 mark[i][j] = !mark[i][j];
>                 for(k = 0;k < 4;k++)
>                 {
>                     mark[i][k] = !mark[i][k];
>                     mark[k][j] = !mark[k][j];
>                 }
>             }
> 
>         }
>     for(i = 0;i < 4;i++)
>         for(j = 0;j < 4;j++)
>             if(mark[i][j] == true)
>             {
>                 ci[nas] = i + 1;
>                 cj[nas] = j + 1;
>                 nas ++;
>             }
>     printf("%d\n",nas);
>     for(i = 0;i < nas;i++)
>     {
>         printf("%d %d\n",ci[i],cj[i]);
>     }
>     return 0;
> }
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 

• Re:那可以快速判断无解的情况吗？ (17) davidtao212 2014-11-12 13:02:45