作者bleed1979 (十三)
看板C_and_CPP
標題Re: [問題] 給一個m*n(m<=n)矩陣，每列取一個非零ꐠ…
時間Sun May 29 00:38:51 2011
不曉得原po是要求所有可能，還是要求幾種可能。
窮舉所有可能，這題解法是DFS。
必須注意的是，如果為稀疏矩陣，是不是可以只儲存對應的元素？
程式碼不到40行，我就直接貼了。
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
vector< vector<int> > M;
string output("A A A A A A A A A A A A A A A A A A A A A A A A A A");
vector<bool> U(26, false);
void dfs(int y, int d) {
if(y == (int)M.size()) {
cout << output.substr(0, d * 2) << "\n";
} else {
for(size_t i = 0; i < M[y].size(); ++i) {
if(!U[M[y][i]]) {
U[M[y][i]] = true;
output[d * 2] += M[y][i];
dfs(y + 1, d + 1);
output[d * 2] = 'A';
U[M[y][i]] = false;
}
}
}
}
int main() {
string s;
while(getline(cin, s, '\n')) {
istringstream stream(s);
vector<int> vec;
int num;
for(int i = 0; stream >> num; ++i) {
if(num > 0) {
vec.push_back(i);
}
}
M.push_back(vec);
}
if(M.size() > 0) {
dfs(0, 0);
}
return 0;
}
至於後者，我想很多高手推文或回文已經給你方向了。
※ 引述《QWWJDQ (夢想十足總是失足)》之銘言：
: 給一個 3*4 矩陣 M, 如下:
: A B C D E
: a 1 1 0 1 0
: M = b 0 0 1 0 0
: c 0 1 0 0 1
: 其中每一列中，1代表可以對應，0代表不可對應。
: 例如:第一列 a 可以對應於 A, B, D，不可對應於C, E。
: 欲求 a,b,c 一一對應(one-to-one)於 A,B,C,D,E 的所有可能。
: 也就是有如下結果：
: a b c, a b c, a b c, a b c, a b c
: | | | | | | | | | | | | | | |
: A C B, A C E, B C E, D C B, D C E
: 共五種。
: 想請問，這種問題適合用遞迴嗎，特別是當矩陣大小達到20*33時？
: 有沒有類似問題的演算法？
: 如果要用遞迴的話，我的想法是：
: 矩陣M中的第一列，有"三個"非零元素，
: A B C D E
: a 1 1 0 1 0
: M = b 0 0 1 0 0
: c 0 1 0 0 1
: for i = 1 to "3"
: if !(M包含某列元素皆為0)
: {
: 1.取第i個非零元素, i=1 時為 M(a,A), 紀錄此mapping (a,A)
: 2.將第a列,第A行刪除,得:
: B C D E
: M = b 0 1 0 0
: c 1 0 0 1
: 3. 再用此M去遞迴
: 其中,當M為空時, 列出mapping結果.
: }
: 不知道這樣的想法OK不OK，
: 因為其中有個for loop，所以不知道該怎麼把mapping的過程記錄下來。
: 這個演算法我之後希望能套用到一個較大SIZE的矩陣(20*33)，複雜度很高，
: 我有嘗試過用queue和stack的方式做，在小矩陣上OK，
: 換了大矩陣後，跑了一天還沒跑完，
: 不知道有沒有高手可以提供一點意見，感激不盡。
: *第一次PO文，不知道這問題適不適合在這個版上，還請見諒。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.114.186
→ bleed1979:抱歉，我忽略了重複的部分，再寫過。 05/29 00:41
※ 編輯: bleed1979 來自: 114.43.114.186 (05/29 00:51)
→ bleed1979:原文已修改。 05/29 00:51
※ 編輯: bleed1979 來自: 114.43.114.186 (05/29 00:54)
→ firejox:我擔心string放裏面會有記憶體吃不消的問題... 05/29 00:55
※ 編輯: bleed1979 來自: 114.43.114.186 (05/29 01:14)
→ bleed1979:感謝指點，還是力求精進比較好。 05/29 01:15
→ loveme00835:因為有就用 vs 懂了才用, 是兩碼子事 05/29 02:00