UVA - 1609 Foul Play——思路题

UVA - 1609 Foul Play——思路题

挺好的思路题， 题解紫书249页写的很明白，不过推荐自己先想一下

#include #include #include #include #include using namespace std;typedef pair P;const int maxn = 1300;bool vis[maxn];char str[maxn][maxn];int n, a[maxn][maxn];int cnt, pos[maxn];vector

match[maxn];int main() { int change[maxn]; change[2] = 1, change[4] = 2, change[8] = 3, change[16] = 4, change[32] = 5; change[64] = 6, change[128] = 7, change[256] = 8, change[512] = 9, change[1024] = 10; while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) scanf("%s", str[i] + 1); int m = change[n]; memset(vis, false, sizeof(vis)); memset(a, 0, sizeof(a)); for (int i = 0; i <= m; i++) match[i].clear(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = str[i][j] - '0'; } } for (int k = 1; k <= m; k++) { //step1: for (int i = 1; i <= n; i++) { if (vis[i] || a[1][i]) continue; for (int j = 1; j <= n; j++) { if (vis[j] || !a[j][i] || !a[1][j]) continue; vis[i] = vis[j] = true; match[k].push_back(make_pair(j, i)); break; } } //step2: for (int i = 2; i <= n; i++) { if (vis[i] || !a[1][i]) continue; match[k].push_back(make_pair(1, i)); vis[i] = true; break; } //step3: cnt = 0; for (int i = 2; i <= n; i++) { if (vis[i] || a[1][i]) continue; pos[++cnt] = i; } for (int i = 1; i < cnt; i+=2) { vis[pos[i]] = vis[pos[i+1]] = true; if (!a[pos[i]][pos[i + 1]]) swap(pos[i], pos[i + 1]); match[k].push_back(make_pair(pos[i], pos[i + 1])); } //step4: cnt = 0; for (int i = 2; i <= n; i++) { if (!vis[i]) pos[++cnt] = i; } for (int i = 1; i <= cnt; i+=2) { vis[pos[i]] = vis[pos[i + 1]] = true; if (!a[pos[i]][pos[i+1]]) swap(pos[i], pos[i + 1]); match[k].push_back(make_pair(pos[i], pos[i + 1])); } //last for (unsigned int i = 0; i < match[k].size(); i++) { int index = match[k][i].first; vis[index] = false; } } for (int i = 1; i <= m; i++) { for (unsigned int j = 0; j < match[i].size(); j++) { printf("%d %d\n", match[i][j].first, match[i][j].second); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。