fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <set>
  6. using namespace std;
  7.  
  8. struct Point {
  9.     int r, c;
  10.     bool operator<(const Point& o) const {
  11.         return r != o.r ? r < o.r : c < o.c;
  12.     }
  13. };
  14.  
  15. class PuzzleSolver {
  16.     int N, M;
  17.     vector<vector<vector<string>>> pieces; // FIXED: Changed to 3D vector
  18.     vector<vector<int>> board;
  19.     int totalTiles = 0;
  20.  
  21.     // Normalize piece to top-left corner
  22.     vector<string> normalize(vector<string> piece) {
  23.         int minR = N, minC = N, maxR = -1, maxC = -1;
  24.         for (int i = 0; i < piece.size(); i++) {
  25.             for (int j = 0; j < piece[i].size(); j++) {
  26.                 if (piece[i][j] == '#') {
  27.                     minR = min(minR, i);
  28.                     maxR = max(maxR, i);
  29.                     minC = min(minC, j);
  30.                     maxC = max(maxC, j);
  31.                 }
  32.             }
  33.         }
  34.  
  35.         vector<string> result(maxR - minR + 1, string(maxC - minC + 1, '.'));
  36.         for (int i = minR; i <= maxR; i++) {
  37.             for (int j = minC; j <= maxC; j++) {
  38.                 if (piece[i][j] == '#') {
  39.                     result[i - minR][j - minC] = '#';
  40.                 }
  41.             }
  42.         }
  43.         return result;
  44.     }
  45.  
  46.     // Rotate piece 90 degrees clockwise
  47.     vector<string> rotate(const vector<string>& piece) {
  48.         int h = piece.size();
  49.         int w = piece[0].size();
  50.         vector<string> rotated(w, string(h, '.'));
  51.  
  52.         for (int i = 0; i < h; i++) {
  53.             for (int j = 0; j < w; j++) {
  54.                 rotated[j][h - 1 - i] = piece[i][j];
  55.             }
  56.         }
  57.         return normalize(rotated);
  58.     }
  59.  
  60.     // Generate all unique rotations
  61.     vector<vector<string>> getRotations(vector<string> piece) {
  62.         set<vector<string>> unique;
  63.         vector<string> current = normalize(piece);
  64.  
  65.         for (int i = 0; i < 4; i++) {
  66.             unique.insert(current);
  67.             current = rotate(current);
  68.         }
  69.  
  70.         return vector<vector<string>>(unique.begin(), unique.end());
  71.     }
  72.  
  73.     // Check if piece can be placed at position (r, c)
  74.     bool canPlace(const vector<string>& piece, int r, int c) {
  75.         int h = piece.size();
  76.         int w = piece[0].size();
  77.  
  78.         if (r + h > N || c + w > N) return false;
  79.  
  80.         for (int i = 0; i < h; i++) {
  81.             for (int j = 0; j < w; j++) {
  82.                 if (piece[i][j] == '#' && board[r + i][c + j] != 0) {
  83.                     return false;
  84.                 }
  85.             }
  86.         }
  87.         return true;
  88.     }
  89.  
  90.     // Place piece on board
  91.     void place(const vector<string>& piece, int r, int c, int pieceId) {
  92.         int h = piece.size();
  93.         int w = piece[0].size();
  94.         for (int i = 0; i < h; i++) {
  95.             for (int j = 0; j < w; j++) {
  96.                 if (piece[i][j] == '#') {
  97.                     board[r + i][c + j] = pieceId;
  98.                 }
  99.             }
  100.         }
  101.     }
  102.  
  103.     // Remove piece from board
  104.     void remove(const vector<string>& piece, int r, int c) {
  105.         int h = piece.size();
  106.         int w = piece[0].size();
  107.         for (int i = 0; i < h; i++) {
  108.             for (int j = 0; j < w; j++) {
  109.                 if (piece[i][j] == '#') {
  110.                     board[r + i][c + j] = 0;
  111.                 }
  112.             }
  113.         }
  114.     }
  115.  
  116.     // Count tiles in piece
  117.     int countTiles(const vector<string>& piece) {
  118.         int count = 0;
  119.         for (const auto& row : piece) {
  120.             for (char c : row) {
  121.                 if (c == '#') count++;
  122.             }
  123.         }
  124.         return count;
  125.     }
  126.  
  127.     // Backtracking solver
  128.     bool solve(int pieceIdx) {
  129.         if (pieceIdx == M) {
  130.             // Check if all cells are filled
  131.             for (int i = 0; i < N; i++) {
  132.                 for (int j = 0; j < N; j++) {
  133.                     if (board[i][j] == 0) return false;
  134.                 }
  135.             }
  136.             return true;
  137.         }
  138.  
  139.         // Try all rotations of current piece
  140.         for (const auto& rotation : pieces[pieceIdx]) {
  141.             // Try all positions
  142.             for (int r = 0; r < N; r++) {
  143.                 for (int c = 0; c < N; c++) {
  144.                     if (canPlace(rotation, r, c)) {
  145.                         place(rotation, r, c, pieceIdx + 1);
  146.  
  147.                         if (solve(pieceIdx + 1)) {
  148.                             return true;
  149.                         }
  150.  
  151.                         remove(rotation, r, c);
  152.                     }
  153.                 }
  154.             }
  155.         }
  156.  
  157.         return false;
  158.     }
  159.  
  160. public:
  161.     bool solvePuzzle(int n, int m, vector<vector<string>>& inputPieces) {
  162.         N = n;
  163.         M = m;
  164.         board.assign(N, vector<int>(N, 0));
  165.         pieces.clear();
  166.         totalTiles = 0;
  167.  
  168.         // Preprocess pieces: generate all rotations
  169.         for (auto& piece : inputPieces) {
  170.             vector<string> normalized = normalize(piece);
  171.             totalTiles += countTiles(normalized);
  172.             pieces.push_back(getRotations(normalized));
  173.         }
  174.  
  175.         // Early exit: check if total tiles match board size
  176.         if (totalTiles != N * N) {
  177.             return false;
  178.         }
  179.  
  180.         return solve(0);
  181.     }
  182. };
  183.  
  184. int main() {
  185.     ios_base::sync_with_stdio(false);
  186.     cin.tie(NULL);
  187.  
  188.     int N, M;
  189.     cin >> N >> M;
  190.     cin.ignore();
  191.  
  192.     vector<vector<string>> pieces(M);
  193.     for (int i = 0; i < M; i++) {
  194.         vector<string> piece(N);
  195.         for (int j = 0; j < N; j++) {
  196.             getline(cin, piece[j]);
  197.         }
  198.         pieces[i] = piece;
  199.     }
  200.  
  201.     PuzzleSolver solver;
  202.     if (solver.solvePuzzle(N, M, pieces)) {
  203.         cout << "yes" << endl;
  204.     } else {
  205.         cout << "no" << endl;
  206.     }
  207.  
  208.     return 0;
  209. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
4 4
.#..
.##.
.#..
....
.#..
.##.
....
....
....
..#.
..#.
###.
....
.#..
.#..
.##.
stdout
copy 
yes
https://ideone.com/di9yBi
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!