(14601) 샤워실 바닥 깔기 (Large)

https://www.acmicpc.net/problem/14601

단계별로 풀어보기

37단계(해 구성하기) 10번째

 

 

 

ㄱ자 모양의 타일 4개로 2배 큰 ㄱ자 모양을 만들 수 있는 건 유명한 퍼즐이다. 이를 이용해 재귀로 풀면 된다.

애드 혹에 정답은 없다. 잘 구현하자.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int k, x, y, cnt= 1;
  
  cin >> k >> x >> y;
  
  int len= 1<<k;
  x--;
  y--;
  vector v(len, vector<int> (len));
  v[y][x]= -1;
  
  auto func= [&](auto self, int xs, int xe, int ys, int ye, int a) -> void {
    if(xs+1==xe){
      if(a!=1)  v[ys][xs]= cnt;
      if(a!=2)  v[ys][xe]= cnt;
      if(a!=3)  v[ye][xs]= cnt;
      if(a!=4)  v[ye][xe]= cnt;
      
      cnt++;
      return;
    }
    
    int l= (xe-xs)/2;
    
    if(a!=1)  self(self, xs, xs+l, ys, ys+l, 4);
    if(a!=2)  self(self, xe-l, xe, ys, ys+l, 3);
    if(a!=3)  self(self, xs, xs+l, ye-l, ye, 2);
    if(a!=4)  self(self, xe-l, xe, ye-l, ye, 1);
    self(self, xs+(l+1)/2, xe-(l+1)/2, ys+(l+1)/2, ye-(l+1)/2, a);
  };
  
  int xl= 0, xr= len-1, yl= 0, yr= len-1, l;
  do{
    l= (xr-xl)/2;
    
    if(x<=xl+l && y<=yl+l){
      func(func, xl, xr, yl, yr, 1);
      xr= xl+l;
      yr= yl+l;
    }else if(y<=yl+l){
      func(func, xl, xr, yl, yr, 2);
      xl= xr-l;
      yr= yl+l;
    }else if(x<=xl+l){
      func(func, xl, xr, yl, yr, 3);
      xr= xl+l;
      yl= yr-l;
    }else{
      func(func, xl, xr, yl, yr, 4);
      xl= xr-l;
      yl= yr-l;
    }
  }while(l);
  
  for(int i=len-1;i>=0;i--){
    for(int j=0;j<len;j++){
      cout << v[i][j] << " ";
    }
    cout << "\n";
  }
  
  return 0;
}