学步园

题意：在M*N的矩阵中，每个元素为０或１,现在问你能否找到若干行，使得每一列只有１个１.

思路：bfs + 优先队列

源代码：

#include <iostream><br /> #include <cstring><br /> #include <cstdio><br /> #include <queue><br /> using namespace std;<br /> const int MAXN = 17;<br /> const int MAXM = 301;<br /> int matrix[MAXN][MAXM];<br /> int link[MAXN][MAXN]; //判断i行和j行能否组合<br /> int rowCnt[MAXN]; //rowCnt判断i行中1的总数<br /> int m, n;<br /> struct node_T {<br /> int row[MAXN]; //记录已经合并哪些行<br /> int rCnt; //记录行的记录数<br /> int cnt; //记录列中1的总数<br /> bool operator < (const node_T &nod) const //运算符重载<br /> {<br /> return cnt < nod.cnt;<br /> }<br /> };<br /> bool bfs()<br /> {<br /> priority_queue<node_T> Q; //优先级队列<br /> node_T cur, tmp;<br /> int i, j;<br /> for(i = 0; i < m; i ++)<br /> {<br /> cur.row[0] = i; //初始化队列，每行入队列<br /> cur.rCnt = 1;<br /> cur.cnt = rowCnt[i];<br /> Q.push(cur);<br /> }<br /> while(! Q.empty())<br /> {<br /> cur = Q.top();<br /> Q.pop();<br /> if(cur.cnt == n)<br /> return true;<br /> tmp = cur;<br /> for(i = cur.row[cur.rCnt - 1] + 1; i < m; i ++)<br /> {<br /> for(j = 0; j < cur.rCnt; j ++)<br /> {<br /> if(! link[i][cur.row[j]]) //两行可以放在一起<br /> break;<br /> }<br /> if(j == cur.rCnt)<br /> {<br /> tmp.rCnt = cur.rCnt + 1; //添加一行到结构中，记录在结构中<br /> tmp.row[tmp.rCnt - 1] = i;<br /> tmp.cnt = cur.cnt + rowCnt[i];<br /> Q.push(tmp); //加入队列中<br /> }<br /> }<br /> }<br /> return false;<br /> }<br /> int main()<br /> {<br /> int i, j, k;<br /> while(scanf("%d%d", &m, &n) != EOF)<br /> {<br /> memset(rowCnt, 0, sizeof(rowCnt));<br /> for(i = 0; i < m; i ++)<br /> {<br /> for(j = 0; j < n; j ++)<br /> {<br /> scanf("%d", &matrix[i][j]);<br /> rowCnt[i] += matrix[i][j];<br /> }<br /> }<br /> for(i = 0; i < m; i ++)<br /> {<br /> link[i][i] = 0;<br /> for(j = i + 1; j < m; j ++)<br /> {<br /> for(k = 0; k < n; k ++)<br /> {<br /> if(matrix[i][k] & matrix[j][k]) break;<br /> }<br /> if(k < n)<br /> {<br /> link[i][j] = link[j][i] = 0;<br /> }<br /> else<br /> {<br /> link[i][j] = link[j][i] = 1;<br /> }<br /> }<br /> }<br /> if(bfs())<br /> printf("Yes, I found it/n");<br /> else<br /> printf("It is impossible/n");<br /> }<br /> return(0);<br /> }