题意:
给定一个 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;
}

京公网安备 11010502036488号