题目题意

有一个n*m的01矩阵,从点(i,j)出发是否能找到一个点(x,y),并且保证从起始点到终止点的简单路径组成的字符串能够使之成为一个回文串。

题目要求

判断每个点是否能依据题意组成一个回文串,如果可以,则输出'Y',否则,输出'N'。

题目分析

根据题意,我们是不可以单个点组成一个回文串的,也就是说组成的回文串要 >=2 的,比如:11,00,101,100001等,那么,如果开头是1,结尾必须要为1才行,0亦是如此,所以需要组成一个回文串,那么1/0的个数就需要 >=2 ,一旦<=1 就不可能组成,当1/0的个数大于1时,我们只需找到离最近的1/0就可以组成一个回文串,所以根据这个思路,我们可以得到如下代码:

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n,m;
    scanf("%d%d",&n,&m);
    vector<string>s(n,string(m,'0'));  //初始化字符串,避免空字符串访问越界
    int cnt_1=0,cnt_0=0;   //用来计数1和0的个数
    for(int i=0;i<n;i++){
        scanf("%s",&s[i][0]);
        for(int j=0;j<m;j++){
            if(s[i][j]=='1') cnt_1++; //计1的个数
            else cnt_0++;  //计0的个数
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='1'){
                printf("%c",cnt_1>1?'Y':'N');  //如果1的个数大于1,则输出"Y",否则输出"N"
            }else{
                printf("%c",cnt_0>1?'Y':'N');  //如果0的个数大于1,则输出"Y",否则输出"N"
            }
        }
        printf("\n");
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
}