题意：
给你一些小方块,问是不是能组成一个4X4的大方块,所有方块全部要使用,裸枚举
#include#include #include using namespace std;const int NN = 20;class Piece{ private: int r; int c; int** p; public: Piece() : r(0), c(0) { p = NULL; } Piece(int r, int c, int (*pp)[NN]) { this->r = r; this->c = c; this->p = new int*[r]; for(int i = 0; i < r; i++) { this->p[i] = new int[c]; memcpy(this->p[i], pp[i], c * sizeof(int)); } } ~Piece() { for(int i = 0; i < r; i++) delete[] p[i]; delete this->p; } int getR() { return this->r; } int getC() { return this->c; } int ** getP() { return this->p; }};int N;int r, c;int m[6][6];int vis[NN];Piece* piece[NN];int pi = 0;void dump(){ for(int i = 0; i < pi; i++) for(int j = 0; j < piece[i]->getR(); j++) { for(int k = 0; k < piece[i]->getC(); k++) cout << piece[i]->getP()[j][k]; cout << endl; }}bool judge(int y, int x, Piece* p){ for(int i = 0; i < p->getR(); i++) for(int j = 0; j < p->getC(); j++) if(p->getP()[i][j] != 0 && m[i + y][x + j] != 0) { return false; } return true;}void reset(int x, int y, int r, int c, int cur){ for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) { if(m[y + i][x + j] != cur) continue; m[y + i][x + j] = 0; }}void copy(int x, int y, int r, int c, int** src){ for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) { if(m[y + i][x + j]) continue; m[y + i][x + j] = src[i][j]; }}bool dfs(int cur){ if(cur == pi) { for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) if(m[i][j] == 0) return false; } return true; } //对当前的cur,枚举每一个坐标X,Y for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { if(m[i][j] && (piece[cur]->getP()[0][0])) continue; if(!judge(i, j, piece[cur])) continue; int r = piece[cur]->getR(); int c = piece[cur]->getC(); copy(j, i, r, c, piece[cur]->getP()); int ok = dfs(cur + 1); if(ok) return ok; reset(j, i, r, c, cur + 1); } } return false;}int main(){ //freopen("d://1.text", "r", stdin); int t = 0; while (cin >> N && N) { if(t != 0) cout << endl; ++t; memset(m, 0, sizeof(m)); memset(piece, 0, sizeof(piece)); memset(vis, 0, sizeof(vis)); int p[NN][NN]; pi = 0; for(int i = 1; i <= N; i++) { scanf("%d %d", &r, &c); for(int j = 0; j < r; j++) for(int k = 0; k < c; k++) { char t; cin >> t; if(t == '0') p[j][k] = 0; else p[j][k] = i; } Piece* pp = new Piece(r, c, p); piece[pi++] = pp; } bool ok = dfs(0); if(!ok) { cout << "No solution possible" << endl; } else { for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) cout << m[i][j]; cout << endl; } } }// dump(); return 0;}
posted on 2018-06-24 18:41 阅读( ...) 评论( ...)