# A nice backtracking problem

## AtCoder: D — Polyomino

This is the question D of basic contest from AtCoder (ABC322).

D — Polyomino

# Solution

It can use backtracking to solve this problem. However, as we have to do some preparation job, the code is a bit long.

`#include<iostream>                                                                      #include<vector>                                                                        #include<set>                                                                           #include<algorithm>                                                                     using namespace std;                                                                    typedef pair<int, int> PII;                                                                                                                                                     vector<PII> norm(vector<PII> ret){                                                          vector<PII>fin_ret;                                                                     int min_i = 100, min_j = 100;                                                           for (auto [i, j]:ret){                                                                      min_i = min(i, min_i);                                                                  min_j = min(j, min_j);                                                              }                                                                                       for (auto [a, b]: ret){                                                                     fin_ret.emplace_back(a - min_i, b - min_j);                                         }                                                                                       sort(fin_ret.begin(), fin_ret.end());                                                   return fin_ret;                                                                     }                                                                                       vector<PII> get_p(vector<string>grid){                                                      vector<PII>ret;                                                                         vector<PII>fin_ret;                                                                     for (int i = 0; i < 4;++i){                                                                 for (int j = 0; j < 4;++j){                                                                 if (grid[i][j] == '.')continue;                                                         ret.emplace_back(i, j);                                                             }                                                                                   }                                                                                       return norm(ret);                                                                   }                                                                                                                                                                               vector<PII>rotate_90(vector<PII>&pattern){                                                  vector<PII>ret;                                                                         for (auto [y, x]: pattern){                                                                 /*                                                                                         90° clockwise rotation: (𝑥,𝑦)                                                           becomes (𝑦,−𝑥)                                                                          */                                                                                   ret.emplace_back(-x, y);                                                            }                                                                                       return norm(ret);                                                                   }                                                                                                                                                                                                                                                                       set<vector<PII>> get_c(vector<PII>pattern){                                                 set<vector<PII>> ret;                                                                   ret.insert(pattern);                                                                    auto new_pattern90 = rotate_90(pattern);                                                auto new_pattern180 = rotate_90(new_pattern90);                                         auto new_pattern270 = rotate_90(new_pattern180);                                        auto new_pattern360 = rotate_90(new_pattern270);                                        ret.insert(new_pattern90);                                                              ret.insert(new_pattern180);                                                             ret.insert(new_pattern270);                                                             ret.insert(new_pattern360);                                                             return ret;                                                                         }                                                                                                                                                                               void update_c(vector<PII>&c, vector<vector<int>> &seen, int i, int j, int v){               for (auto [di, dj]:c){                                                                      seen[i + di][j + dj] = v;                                                           }                                                                                   }                                                                                       bool can_put(vector<PII>&c, vector<vector<int>> &seen, int i, int j){                       for (auto [di, dj]:c){                                                                      int ii = i + di, jj = j +dj;                                                            if (ii < 0 || ii >= 4 || jj <0 || jj >= 4 || seen[ii][jj])return false;             }                                                                                       return true;                                                                        }                                                                                       bool dfs(vector<vector<vector<PII>>>&steps,  vector<vector<int>> &seen, vector<int>&seen_step){    for (int i = 0; i < 4;++i){                                                                 for (int j = 0; j < 4; ++j){                                                                if (seen[i][j])continue;                                                                for (int step = 0; step < 3; ++step){                                                       if (seen_step[step])continue;                                                           for (auto c: steps[step]){                                                                  if (can_put(c, seen, i, j)){                                                                seen_step[step] = 1;                                                                    if (seen_step[0] == 1 && seen_step[1] == 1 && seen_step[2] == 1)return true;                        update_c(c, seen, i, j, 1);                                                             if (dfs(steps, seen, seen_step)){                                                           return true;                                                                        }                                                                                       seen_step[step]=false;                                                                  update_c(c, seen, i, j, 0);                                                         }                                                                                   }                                                                                   }                                                                                   }                                                                                   }                                                                                       return false;                                                                       }                                                                                       int main(){                                                                                 vector<string>grid(4);                                                                  vector<vector<PII>> patterns;                                                           int cnt = 0;                                                                            for (int i = 0; i <3;++i){                                                                  for (int j = 0; j < 4;++j){                                                                 cin >> grid[j];                                                                         for (int jj = 0; jj < 4;++jj){                                                              if (grid[j][jj] == '#')cnt ++;                                                      }                                                                                   }                                                                                       patterns.push_back(get_p(grid));                                                    }                                                                                       if (cnt != 16){                                                                             cout <<"No"<<endl;                                                                      return 0;                                                                           }                                                                                       vector<set<vector<PII>>> candidates(3);                                                 for (int i = 0; i < 3; ++i){                                                                candidates[i] = get_c(patterns[i]);                                                 }                                                                                       vector<vector<vector<PII>>> steps(3);                                                   for (int i = 0; i < 3;++i){                                                                 for (auto c: candidates[i]){                                                                steps[i].push_back(c);                                                              }                                                                                   }                                                                                       vector<vector<int>> seen(4, vector<int>(4, 0));                                         vector<int>seen_step(3, 0);                                                             auto ret = dfs(steps, seen, seen_step);                                                 string fin_ret = ret?"Yes":"No";                                                        cout << fin_ret << endl;                                                                return 0;                                                                           }                                                                                   `

--

--