CF645A

Zhouyc2009 · 2021-07-15 11:18:33 · 题解

背景：本蒟蒻从月赛后找到了本题。

前缀知识(移动中要使用）：异或运算

理解题意：

题目输入两个 2\times2 的矩阵，问矩阵 A 是否能通过移动变成矩阵 B ，能输出 YES ，不能输出 NO 。

思路（用了种很神奇的方法）：

用随机数枚举 10000 次移动，然后每次与 B 数组比较是否相同，最后输出就行了。本蒟蒻也不知道具体移动几次，但定的大点总没事，O(n) 的时间复杂度也不会超时。

CODE:

#include<bits/stdc++.h>
using namespace std;
char a[2][2],b[2][2];//定义两个数组。
int f;
int main()
{
    cin>>a[0][0]>>a[0][1]>>a[1][0]>>a[1][1]>>b[0][0]>>b[0][1]>>b[1][0]>>b[1][1];//奇奇怪怪的输入，不想打循环。
    for(int _=1; _<=100000;_++) {
        int i=rand()%2;
        int j=rand()%2;//两个随机数。
        if(a[i][j]!=0)
         {
            if (rand()%2==0)
             {
                if(a[i][j^1]=='X')//异或移动。
                 {
                    a[i][j^1]=a[i][j];
                    a[i][j]='X';
                 }
             } 
             else if(a[i^1][j]=='X')
              {
                a[i^1][j]=a[i][j];
                a[i][j]='X';
              }
        }//移动。
        f=0;//每次判断前清0也可以用bool类型判断。
        for(int i=0;i<2;++i)
            for(int j=0;j<2;++j)
                if(a[i][j]!=b[i][j]){
                    f=1;
                    break;
                }//是否相等
        if(f==0)
          {
            cout<<"YES";
            return 0;
        }//要移动的话就输出YES，并结束程序。
    }
    cout<<"NO";//运行到这里就可以输出NO了。
    return 0;
}

结束啦~