블록이동하기

programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

아직 미해결 해결중입니다..

#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

typedef struct loc{
    int x1;
    int y1;
    int x2;
    int y2;
} loc;

int dx[] = {-1,1,1,-1};
int dy[] = {1,1,-1,-1};

int dlx[] = {-1,-1,1,1};
int dly[] = {-1,1,1,-1};

int mdx[] = {0,1,-1,0};
int mdy[] = {1,0,0,-1};

int bfs(loc robot,vector<vector<int>>& board,map<pair<pair<int,int>,pair<int,int>>,int>&check){

    int n = board.size();
    queue<loc>q;
    q.push(robot);
    int x1,y1,x2,y2;
    while(!q.empty()){
        
        loc l = q.front();
        q.pop();
        x1 = l.x1;
        y1 = l.y1;
        x2 = l.x2;
        y2 = l.y2;
        
     
  //      cout<<x1<<" "<<y1<<" ";
  //      cout<<x2<<" "<<y2<<endl;
        
        pair<pair<int,int>,pair<int,int>> origin =  make_pair(make_pair(x1,y1),make_pair(x2,y2));
        
        if((x1==n && y1==n) ||(x2==n && y2==n)){
            return check[origin];
        }
        
        
        int nx1 = x1;
        int ny1 = y1;
    
        //x2,y2 기준 회전
        for(int i=0; i<4; i++){
             nx1 = nx1+dx[i];
             ny1 = ny1+dy[i];
            if(nx1>=1 && nx1<=n && ny1>=1 && ny1<=n && board[nx1-1][ny1-1]==0  && (abs(nx1-x2)+abs(ny1-y2))==1){
                int ndlx = x1 + dlx[i];
                int ndly = y1 +dlx[i];
                if(ndlx>=1 && ndlx<=n &&ndly>=1 && ndly<=n ){
                  pair<pair<int,int>,pair<int,int>> loca =  make_pair(make_pair(nx1,ny1),make_pair(x2,y2));
                  pair<pair<int,int>,pair<int,int>> rloca = make_pair(make_pair(x2,y2),make_pair(nx1,ny1));
                    if(board[ndlx-1][ndly-1]==0 && check.find(loca)==check.end()){
                        check[loca] = check[origin]+1;
                        check[rloca] = check[origin]+1;
                        loc newl;
                        newl.x1 = nx1;
                        newl.y1 = ny1;
                        newl.x2 = x2;
                        newl.y2 = y2;
                        q.push(newl);
                    }
                }
            }
           
            }
        
         int nx2 = x2;
        int ny2 = y2;
        
        //x1,y1 기준 회전
        for(int i=0; i<4; i++){
             nx2 = nx2+dx[i];
             ny2 = ny2+dy[i];
            if(nx2>=1 && nx2<=n && ny2>=1 && ny2<=n && board[nx2-1][ny2-1]==0 && (abs(x1-nx2)+abs(y1-ny2))==1){
                int ndlx = x2 + dlx[i];
                int ndly = y2 +dlx[i];
                if(ndlx>=1 && ndlx<=n &&ndly>=1 && ndly<=n){
                  pair<pair<int,int>,pair<int,int>> loca =  make_pair(make_pair(x1,y1),make_pair(nx2,ny2));
                 pair<pair<int,int>,pair<int,int>> rloca = make_pair(make_pair(nx2,ny2),make_pair(x1,y1));
                    if(board[ndlx-1][ndly-1]==0 && check.find(loca)==check.end()){
                        check[loca] = check[origin]+1;
                        check[rloca] = check[origin]+1;
                        loc newl;
                        newl.x1 = x1;
                        newl.y1 = y1;
                        newl.x2 = nx2;
                        newl.y2 = ny2;
                        q.push(newl);
                    }
                }
            }
           
            }
        
        //이동
        for(int i=0; i<4; i++){
           int nx1 = x1+ mdx[i];
           int ny1 = y1+ mdy[i];
           int nx2 = x2+ mdx[i];
           int ny2 = y2+ mdy[i];
           if(nx1>=1 && nx1<=n && ny1>=1 && ny1<=n && nx2>=1 && nx2<=n && ny2>=1 && ny2<=n ){
                pair<pair<int,int>,pair<int,int>> loca = make_pair(make_pair(nx1,ny1),make_pair(nx2,ny2));
               pair<pair<int,int>,pair<int,int>> rloca = make_pair(make_pair(nx2,ny2),make_pair(nx1,ny1));
               if(board[nx1-1][ny1-1]==0 && board[nx2-1][ny2-1]==0 && check.find(loca)==check.end()){
                  check[loca] = check[origin]+1;
                    check[rloca] = check[origin]+1;
                   loc newl;
                    newl.x1 = nx1;
                    newl.y1 = ny1;
                    newl.x2 = nx2;
                    newl.y2 = ny2;
                     q.push(newl);
                   
               }
           }
        }
        
        
        
        }
        return -1;
    }







int solution(vector<vector<int>> board) {
    int answer = 0;
    loc robot;
    
    robot.x1 = 1;
    robot.y1 =1;
    robot.x2 =1;
    robot.y2 =2;
    
    map<pair<pair<int,int>,pair<int,int>>,int>check;
    pair<pair<int,int>,pair<int,int>> origin =  make_pair(make_pair(robot.x1,robot.y1),make_pair(robot.x2,robot.y2));
     pair<pair<int,int>,pair<int,int>> rorigin =  make_pair(make_pair(robot.x2,robot.y2),make_pair(robot.x1,robot.y1));
    check[origin]=0;
    check[rorigin]=0;
    answer = bfs(robot,board,check);
    
   
    return answer;
}