数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：判断给定矩阵是否可以构成回文矩阵
假设我们有一个维度为h x w的矩阵，矩阵包含英文字母。我们必须创建一个另一个矩阵，该矩阵包含回文行和回文列，即每一行和每一列都是回文。为此，可以对给定矩阵的行和列进行任何排列；但不能更改任何元素，例如'a'不能更改为'b'。如果可以从给定矩阵创建一个回文矩阵，则返回true；否则，返回false。
因此，如果输入类似于h = 4，w = 4，mat = {"xxyy", "xyxx", "yxxy", "xyyy"}，则输出为true。
步骤
为了解决这个问题，我们将遵循以下步骤：
Define one map mp
Define an array count of size 4.
for initialize i := 0, when i < h, update (increase i by 1), do:
for initialize j := 0, when j < w, update (increase j by 1), do:
(increase tp[mat[i, j]] by 1)
for each value val in tp, do:
increase count[second value of val mod 4] by 1
check := true
if h mod 2 is same as 0 and w mod 2 is same as 0, then:
if count[1] + count[2] + count[3] > 0, then:
check := false
otherwise when h mod 2 is same as 1 and w mod 2 is same as 1, then:
if count[1] + count[3] > 1, then:
check := false
otherwise when count[2] > h / 2 + w / 2, then:
check := false
Otherwise
if count[1] + count[3] > 0, then:
check := false
otherwise when h mod 2 is same as 1 and count[2] > w / 2, then:
check := false
otherwise when w mod 2 is same as 1 and count[2] > h / 2, then:
check := false
return check示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
bool solve(int h, int w, vector<string> mat){
map<char, int> tp;
vector<int> count(4);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j)
tp[mat[i][j]]++;
}
for (auto val : tp)
count[val.second % 4]++;
bool check = true;
if (h % 2 == 0 && w % 2 == 0) {
if (count[1] + count[2] + count[3] > 0)
check = false;
}
else if (h % 2 == 1 && w % 2 == 1) {
if (count[1]+count[3] > 1)
check = false;
else if (count[2] > h / 2 + w / 2)
check = false;
} else {
if (count[1] + count[3] > 0)
check = false;
else if (h % 2 == 1 && count[2] > w / 2)
check = false;
else if (w % 2 == 1 && count[2] > h / 2)
check = false;
}
return check;
}
int main() {
int h = 4, w = 4;
vector<string> mat = {"xxyy", "xyxx", "yxxy", "xyyy"};
cout<< solve(h, w, mat);
return 0;
}输入
4, 4, {"xxyy", "xyxx", "yxxy", "xyyy"}输出
1
更新于：2022年3月2日
343 次浏览
广告