資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告