// Pizza Boxes -- mjd@cs.auckland.ac.nz // #include #include #include #include #include #include using namespace std; int n, m; // n = #rows, m = #cols inline int at(int i, int j) { return i*m+j; } enum { UNKNOWN, EMPTY, FILLED }; void printboxes(int b[]) { for(int i = 0; i < n; i++) // output board { for (int j=0; j < m; j++) { if (b[at(i,j)]==UNKNOWN) { cout << 'u'; continue; } cout << (b[at(i,j)]==FILLED ? '#' : '-'); } cout << endl; } cout << endl; } int countrow(int b[], int i, int val) { int cnt=0; for (int j=0; j= m) continue; if (b[at(i-k,j+k)]==val) cnt++; } return cnt; } int countdown(int b[], int d, int val) { int cnt=0; int i, j; if (d= n || j+k >= m) continue; if (b[at(i+k,j+k)]==val) cnt++; } return cnt; } void setrow(int b[], int i, int val) { for (int j=0; j= m) continue; if (b[at(i-k,j+k)]==UNKNOWN) b[at(i-k,j+k)]=val; } } void setdown(int b[], int d, int val) { int i, j; if (d= n || j+k >= m) continue; if (b[at(i+k,j+k)]==UNKNOWN) b[at(i+k,j+k)]=val; } } bool issolved(int b[]) { for (int i=0; i &r, const vector &c, const vector &d, const vector &u) { bool changeFlg; do { changeFlg = false; // row check for (int i=0; i &r, const vector &c, const vector &d, const vector &u, int k) { if (!(k < m*n)) { cerr << "no solution!\n"; } bool ans = propagate(b, r, c, d, u); // first solution if (ans == true) return true; tryagain: // backtracking code that probably isn't required int k2=-1; for (int i=k; i> n >> m; if (n==0 && m==0) break; num++; vector r(n); vector c(m); vector d(n+m-1); vector u(n+m-1); int i,t; // input constraints for(i=0; i < n; i++) { cin >> t; r[i] = t; } for(i=0; i < m; i++) { cin >> t; c[i] = t; } for(i=0; i < n+m-1; i++) { cin >> t; d[i] = t; } for(i=0; i < n+m-1; i++) { cin >> t; u[i] = t; } int *b = new int[n*m]; // board for (i=0; i < n*m; i++ ) b[i] = UNKNOWN; solve(b, r, c, d, u, 0); cout << "Pizza box " << num << endl; printboxes(b); delete [] b; } }