题解 | #I 01回文#

题意

在一个01矩阵里，每一个点为起点，看能不能找到另一个点，是的两点简单路径形成的01串为回位串。

关键词

思维

题解

观察01串，若为0开头，二位回文串为00，若未遇到0，则三位为010，同理四位为0110，可以看到01串如果为回文串的话，只要在遇到一个0，即可结束，构成01回文串，同理，1开头的也是如此。

这样这个问题就可以传化成分别计0与1的个数，如果0的个数≥2，则所以0 都是YES,1同理。

#include<bits/stdc++.h>
using namespace std;
string arr[1000005];
int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        int n,m;
        cin>>n>>m;
        int num1=0,num0=0;
        for(int j=1;j<=n;j++){
            cin>>arr[j];
            for(int k=0;k<m;k++){
                if(arr[j][k]=='1') num1++;
                else num0++;
            }
        }
        for(int j=1;j<=n;j++){
            for(int k=0;k<m;k++){
                if(arr[j][k]=='1'){
                    if(num1>=2) cout<<"Y";
                    else cout<<"N";
                }
                else{
                    if(num0>=2) cout<<"Y";
                    else cout<<"N";
                }
            }
            cout<<"\n";
        }
    }
}