// solution written by Michal 'misof' Forisek #include #include #include #include using namespace std; #define FOREACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it) class MaximumMatching { int left_size, right_size; vector< vector > right_to_left; public: MaximumMatching() { left_size=right_size=0; right_to_left.clear(); } void add_edge(int left, int right); vector< pair > maximum_matching(); }; void MaximumMatching::add_edge(int left, int right) { if (left==-1 || right==-1) return; if (left_size <= left) left_size = left+1; if (right_size <= right) { right_size = right+1; right_to_left.resize(right_size); } right_to_left[right].push_back(left); } vector< pair > MaximumMatching::maximum_matching() { int L = left_size, R = right_size; vector match(L,-1); for (int r=0; r from(L,-1); queue Q; FOREACH(it,right_to_left[r]) { Q.push(*it); from[*it]=*it; } while (!Q.empty() && !found) { int l = Q.front(); Q.pop(); if (match[l]==-1) { found = true; while (from[l]!=l) { match[l] = match[from[l]]; l = from[l]; } match[l]=r; } else { FOREACH(it,right_to_left[ match[l] ]) if (from[*it]==-1) { Q.push(*it); from[*it]=l; } } } } vector< pair > result; for (int i=0; i > A; // the map of the island int ENCODE(int r, int c, int n) { return (C*r+c)*5+n; } int LEFT(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,0); else return ENCODE(r,c,1); } int RIGHT(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,0); else return ENCODE(r,c,3); } int TOP(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]==2) return ENCODE(r,c,1); else return ENCODE(r,c,0); } int BOTTOM(int r, int c) { if (A[r][c]==0) return -1; else if (A[r][c]<=2) return ENCODE(r,c,A[r][c]-1); else return ENCODE(r,c,2); } #define VERTEX(r,c,dir) ( ((r<0) || (c<0) || (r>=R) || (c>=C)) ? -1 : dir(r,c) ) int main() { // read the input cin >> R >> C; A.resize(R, vector(C) ); for (int r=0; r> A[r][c]; // create the bipartite graph MaximumMatching MM; for (int r=0; r > matching = MM.maximum_matching(); if (2*matching.size() != expected_size) { cout << "NIE" << endl; return 0; } // from the edges of the matching, reconstruct the map set< pair > edges; FOREACH(it,matching) { edges.insert(make_pair(it->first,it->second)); edges.insert(make_pair(it->second,it->first)); } vector output(3*R, string(3*C,'.')); for (int r=0; r