第39次CSP第二题——水印检查

题目网址https://sim.csp.thusaac.com/contest/39/problem/1以下解答仅供参考#include iostream #include vector #include set using namespace std; int main(){ int n,L; cinnL; // 使用vector容器存储CSP模式 vectorvectorint target{ {1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,1,0,1}, {1,0,0,1,1,1,1,1,0}, {1,0,0,0,0,1,1,0,0}, {1,1,1,1,1,1,1,0,0}, }; // 定义输入的矩阵A vectorvectorint A(n,vectorint(n,0)); for(int i0;in;i){ for(int j0;jn;j){ cinA[i][j]; } } setint res; for(int i0;in-5;i){ // 遍历所有可能的子矩阵左上角行坐标i、子矩阵左上角在大图中的行坐标 for(int j0;jn-9;j){ // 遍历所有可能的子矩阵左上角列坐标j、子矩阵左上角在大图中的列坐标 int k_ubL; // 为1的所有像素灰度值的最小值 int k_lb0; // 为0的所有像素灰度值的最大值 for(int u0;u5;u){ // 像素在子矩阵内的相对行偏移 for(int v0;v9;v){ // 像素在子矩阵内的相对列偏移 if(target[u][v]1){ k_ubmin(k_ub,A[iu][jv]); }else if(target[u][v]0){ k_lbmax(k_lb,A[iu][jv]); } } } // k_lb k k_ub for(int kk_lb1;kk_ub;k){ res.insert(k); } } } for(auto e:res){ couteendl; } return 0; }运行结果以下是其他人的代码仅供参考原作者链接80代码#include iostream #include string #include vector using namespace std; //二值化函数小于k的元素二值化为0大于等于k的元素二值化为1 vectorstring transform(vectorvectorint mat, int k, int n){ vectorstring res(n); for(int i 0; i n; i){ string cur ; for(int j 0; j n; j){ if(mat[i][j] k) cur 1; else cur 0; } res[i] cur; } return res; } //模式匹配函数 //对于给定的起始行x在x行和x4行之间逐行进行模式匹配9个字符串为一组作为匹配单位 bool compare(vectorstring str,vectorstring target,int x){ int num str[x].size(); for(int i 0; i num - 9; i){ bool ans true; for(int j 0; j 4; j){ string sub str[xj].substr(i,9); if(target[j] ! sub){ ans false; break; } } if(ans) return true; } return false; } //主函数 int main(){ int n,L; cin n L; vectorstring target { 111111111, 100100101, 100111110, 100001100, 111111100 }; vectorvectorint mat(n,vectorint(n)); for(int i 0; i n; i){ for(int j 0; j n; j){ cin mat[i][j]; } } for(int k 0; k L; k){ vectorstring strmat transform(mat,k,n); for(int x 0; x n-5; x){ bool cur compare(strmat,target,x); if(cur){ cout k endl; break;//一旦匹配成功即输出当前k值考察下一个k值 } } } return 0; }满分100代码#include vector #include set #include iostream using namespace std; int main(){ vectorvectorint target { {1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,1,0,1}, {1,0,0,1,1,1,1,1,0}, {1,0,0,0,0,1,1,0,0}, {1,1,1,1,1,1,1,0,0} };//目标模式 int n,L; cin n L; vectorvectorint mat(n,vectorint(n,0)); for(int i 0; i n; i){ for(int j 0; j n; j){ cin mat[i][j]; } } setint res; for(int i 0; i n-5; i){ for(int k 0; k n-9; k){ int k_ub L, k_lb 0; //对于每个5 x 9的区域进行上下界取值的初始化 for(int j 0; j 5; j){ for(int h 0; h 9; h){ if(target[j][h] 1){ //更新k_ub k_ub (mat[ij][kh] k_ub) ? mat[ij][kh] : k_ub; } else if(target[j][h] 0){ //更新k_lb k_lb (mat[ij][kh] k_lb) ? mat[ij][kh] : k_lb; } } } //对于每个5 x 9的区域将其对应的所有可行解加入结果中 for(int s k_lb1; s k_ub; s){ res.insert(s); } } } for(auto e : res){ cout e endl; } return 0; }