题意:

给定一个 n×m 的 01 矩阵,针对矩阵中的每一个位置 (i,j),独立判断是否存在非该起点的位置 (x,y),使得从 (i,j) 到 (x,y) 的某条上下左右相邻移动的简单路径上,元素按路径顺序拼接成的字符串为回文串,若存在则输出 Y,不存在则输出 N。

核心思路:

对每个测试用例读取矩阵尺寸n×m,并读入整个 01 矩阵;同时统计矩阵中 0 的总个数c0、1 的总个数c1。 如果矩阵有超过一个 1 ,那任意一个 1 只要找到离他最近的 1 的路径,中间路径可以任意走,一定会构成回文串。

遍历矩阵的每个位置(i,j):

若当前位置值为 1,且全局 1 的总数c1>1,输出Y;否则输出N;

若当前位置值为 0,且全局 0 的总数c0>1,输出Y;否则输出N。

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
inline void optimizeIO() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}
void solve(){
    int n,m;cin>>n>>m;
    char a[n+10][m+10];
    int c0=0,c1=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]=='1'?c1++:c0++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='1'){
                cout<<(c1>1?'Y':'N');
            }else{
                cout<<(c0>1?'Y':'N');
            }
        }
        cout<<endl;
    }
}
 
int main(){
	optimizeIO();
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}