SHISENSHO 도움 부탁 드려요..

  • velopert
    velopert

    일주일동안 잡고 있었는데
    도저히 모르겠네요. 진짜 열심히 디버깅 했는데..

    미로찾기 방식으로 하려니 모르겠어서 루트가 되는 각 케이스를 나누어서
    진행하게끔 했는데요

    예제도 많이 입력해봤는데 자꾸 오답이 나오네요 흑흑
    대체 어떤부분에서 오답이 나오는건지 모르겠어요 ㅠㅠ

    제가 설정한 케이스는요:
    1. 붙어있을때 세로/가로
    2. 1자로 움직일때 세로/가로
    그리고 장애물이 있어서 1자로 못움직일때 [ 모양과 ] 모양
    그리고 그 모양을 90도 돌린 모양
    3. ㄴ 모양 ㄱ 모양으로 움직일때
    4. ㄴ 모양 ㄱ 거울로 비추었을때 모양으로 움직일때
    5. 좌표1 과 좌표2 사이에서 움직이는데..
    아래 오른쪽 아래
    오른쪽 아래 오른쪽
    위 오른쪽 위
    오른쪽 위 오른쪽

    (오른쪽에있는게 무조건 두번째 좌표로 설정됨으로서 좌측으로 움직이는건 생략)
    6. 좌표1과 좌표2 바깥으로 움직이는데
    [ 모양과 ] 모양 근데 비대칭.
    위 모양을 90도 돌린모양.

    이 정도면 모든 케이스를 잡았다고 생각하거든요
    그런데 어느부분에서 오류가 나는건지 자꾸 오답이 뜨네요
    처음부터 코드를 작성하는걸 고려해봐야할까요

    어떤 케이스에서 오류가 뜨는건지.. 도움 부탁드립니다.

    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    class Game{
    
    
        class Item{
            public:
                int x;
                int y;
                char itemType;
                Item(int y, int x, char itemType);
        };
    
        class Board{
    
    
            public:
                int width;
                int height;
                char **map;
                vector<char> itemTypes;
                vector<Item> items;
                Board(int w, int h);
                void setItem(int y, int x, char itemType);
                bool isOpen(int y1, int x1, int y2, int x2);
                bool hasRoute(int y1, int x1, int y2, int x2);
                int getDifficulty();
                void dispose();
                ~Board();
    
        };
    
        public:
            vector<Board> boards;
    
            Game();
            ~Game();
            void readInput();
            void process();
    };
    
    Game::Item::Item(int y, int x, char itemType){
          this->y = y;
          this->x = x;
          this->itemType = itemType;
    }
    
    
    Game::Board::Board(int w, int h){
        width = w;
        height = h;
    
        map = new char*[h];
        for(int i = 0; i < h; i++){
            map[i] = new char[w];
            for(int j = 0; j < w; j++){
                map[i][j] = '.';
            }
        }
    }
    
    void Game::Board::setItem(int y, int x, char itemType){
        // IF ITEM IS NEW, ADD IT TO itemTypes VECTOR;
        if(find(itemTypes.begin(), itemTypes.end(), itemType) == itemTypes.end()){
            itemTypes.push_back(itemType);
        }
    
        Item item(y, x, itemType);
        items.push_back(item);
    
        map[y][x] = itemType;
    }
    
    bool Game::Board::isOpen(int y1, int x1, int y2, int x2){
        if(y1==y2){
            if(x1>x2){
                swap(x1,x2);
                swap(y1,y2);
            }
    
            if(x2-x1==1){
                if(map[y1][x1] == '.' && map[y2][x2] != '.'
                        || map[y1][x1] != '.' && map[y2][x2] == '.'
                        || map[y1][x1] == '.' && map[y2][x2] == '.'){
                    return true;
                }else{
                    return false;
                }
            }
    
            for(int i=x1+1; i<x2; i++){
                if(map[y1][i] != '.')
                    return false;
            }
    
            return true;
        }
    
    
        if(x1==x2){
            if(y1>y2){
                swap(x1,x2);
                swap(y1,y2);
            }
    
            if(y2-y1==1){
                if(map[y1][x1] == '.' && map[y2][x2] != '.'
                        || map[y1][x1] != '.' && map[y2][x2] == '.'){
                    return true;
                }else{
                    return false;
                }
            }
    
            for(int i=y1+1; i<y2; i++){
                if(map[i][x1] != '.')
                    return false;
            }
    
            return true;
        }
    }
    
    bool Game::Board::hasRoute(int y1, int x1, int y2, int x2){
        // CASE 1 : x1 == x2
        if(x1==x2){
    
            // 1.0 STICKED
            if(y2-y1==1||y2-y1==-1){
                 return true;
            }
    
            // 1.1 NO OBSTACLE
            if(isOpen(y1, x1, y2, x2)){
                return 1;
            }
            // 1.2 HAS OBSTACLE
            int i = 1;
            // 1.2.1 LEFT HAND EMPTY
            while(map[y1][x1-i]=='.' && map[y2][x1-i]=='.' && x1-i > -1){
                if(isOpen(y1, x1-i, y2, x1-i)){
                    return 1;
                }
    
                i++;
            }
    
            i = 1;
            // 1.2.2 RIGHT HAND EMPTY
            while(map[y1][x1+i]=='.' && map[y2][x1+i]=='.' && x1+i < width){
                if(isOpen(y1, x1+i, y2, x1+i)){
                   return 1;
                }
                i++;
            }
    
    
            return 0;
        }
    
    
        // CASE 2 : y1 == y2
        if(y1==y2){
    
            if(x2-x1==1||x2-x1==-1){
                 return true;
            }
    
            // 2.1 NO OBSTACLE
            if(isOpen(y1, x1, y2, x2)){
                return 1;
            }
    
            // 2.2 HAS OBSTACLE
            int i = 1;
            // 2.2.1 UP HAND EMPTY
            while(map[y1-i][x1]=='.' && map[y1-i][x2]=='.' && y1-i > -1){
                if(isOpen(y1-i, x1, y1-i, x2)){
                    return 1;
                }
    
                i++;
            }
    
            i = 1;
            // 2.2.2 DOWN HAND EMPTY
            while(map[y1+i][x1]=='.' && map[y1+i][x2]=='.' && y1+i < height){
                if(isOpen(y1+i, x1, y1+i, x2)){
                    return 1;
                }
                i++;
            }
    
            return 0;
        }
    
        // CASE 3 : MOVING DIAGONALLY
    
        // SWAP IF X2 AT LEFT
        if(x1 > x2){
            int tempX = x1;
            int tempY = y1;
    
            x1 = x2;
            y1 = y2;
    
            x2 = tempX;
            y2 = tempY;
    
        }
    
        // CASE 3.1 RIGHT AND DOWN
        if(y2 > y1){
            // 3.1.1 DOWN THEN RIGHT
            if(map[y1+1][x1] == '.' && map[y2][x2-1]){
                if(isOpen(y1,x1,y2,x1))
                    if(isOpen(y2,x1,y2,x2)){
                        return 1;
                     } 
            }
    
            // 3.1.2 RIGHT THEN DOWN
            if(map[y1][x1+1] == '.' && map[y2-1][x2]){
                if(isOpen(y2,x1,y1,x2))
                    if(isOpen(y1,x2,y2,x2)){
                        return 1;
                    } 
            }
    
            //3.1.3 DOWN RIGHT DOWN
            if(map[y1+1][x1] == '.' && map[y2-1][x2] == '.'){
                int a = 1;
                while(map[y1+a][x1]=='.' & y1+a<y2){
                    if(isOpen(y1+a,x1,y1+a,x2))
                        if(isOpen(y1+a,x2,y2,x2)){
                            return 1;
                        } 
                    a++;
                }
            }
    
            // 3.1.4 RIGHT DOWN RIGHT
            if(map[y1][x1+1] =='.' && map[y2][x2-1] == '.'){
                int a = 1;
                while(map[y1][x1+a] == '.' && x1 + a < x2){
                    if(isOpen(y1,x1+a,y2,x1+a))
                        if(isOpen(y2,x1+a,y2,x2)){
                            return 1;
                        }
                    a++;
                }
            }
    
            // return 0;
    
    
    
        }else{
            // CASE 3.2 RIGHT AND UP
    
            // 3.2.1 RIGHT UP
            if(map[y1][x1+1] == '.' && map[y2+1][x2]){
                if(isOpen(y1,x1,y1,x2))
                    if(isOpen(y1,x2,y2,x2))
                    {
                        return 1;
                    }
            }
    
            // 3.2.2 UP RIGHT
            if(map[y1-1][x1] == '.' && map[y2][x2-1]){
                if(isOpen(y1,x1,y2,x1))
                    if(isOpen(y2,x1,y2,x2))
                    {
                        return 1;
                    }
            }
    
            // 3.2.3 UP RIGHT UP
            if(map[y1-1][x1] == '.' && map[y2+1][x2] == '.'){
                int a = 1;
                while(map[y1-a][x1] == '.' && y1-a > y2){
                    if(isOpen(y1-a,x1,y1-a,x2))
                        if(isOpen(y1-a,x2,y2,x2))
                        {
                            return 1;
                        }
                    a++;
                }
            }
    
            // 3.2.4 RIGHT UP RIGHT
            if(map[y1][x1+1] == '.' && map[y2][x2-1]=='.'){
                int a = 1;
                while(map[y1][x1+a] == '.' && x1 + a < x2){
                    if(isOpen(y1,x1+a,y2,x1+a))
                        if(isOpen(y2,x1+a,y2,x2))
                        {
                            return 1;}  
                    a++;
                }
            }
    
           // return 0;
        }
    
    
        // CASE 4 EXCEED/RECEDE AXIS VALUE
    
        // CASE 4.1 EXCEED X2 VALUE: RIGHT DOWN LEFT
        if(isOpen(y1,x1,y1,x2)){
            int a = 1;
            while(map[y1][x2 + a] == '.' && map[y2][x2+a]=='.'
                    && x2 + a < width){
                if(isOpen(y1, x2 + a, y2, x2+a))
    
                    return 1;
                a++;
                if(x2+a>width)
                    break;
            }
        }
    
        // CASE 4.2 RECEDE X1 VALUE : LEFT DOWN RIGHT
        if(isOpen(y2,x2,y2,x1)){
            int a = 1;
    
            while(map[y1][x1 - a] == '.' && map[y2][x1 - a]=='.'
                    && x1 - a >= 0){
    
                if(isOpen(y1, x1 - a, y2, x1 - a))
                    return 1;
                a++;
                if(x1-a==-1)
                    break;
    
            }
        }
    
        // ONE AT THE BOTTOM IS ALWAYS POINT2
        if(y1 > y2){
            swap(y1,y2);
            swap(x1,x2);
        }
    
    
        // CASE 4.3 RECEDE Y1:  UP RIGHT DOWN
        if(isOpen(y2, x2, y1, x2)){
            int a = 1;
            while(map[y1-a][x1] == '.' && map[y1-a][x2]=='.'
                    && y1 - a >= 0){
                if(isOpen(y1 - a, x1, y1-a, x2))
                    return true;
                a++;
                if(y1-a==-1)
                    break;
            }
        }
    
        // CASE 4.4 EXCEED Y2 : DOWN RIGHT UP
        if(isOpen(y1, x1, y2, x1)){
            int a = 1;
            while(y2+a < height){
                if(map[y2+a][x1]!='.' || map[y2+a][x2]!='.')
                    break;
                if(isOpen(y2+a,x1,y2+a,x2))
                    return true;
                a++;
            }
        }
    
    
    
        return 0;
    
    
    }
    
    int Game::Board::getDifficulty(){
        int difficulty = 0;
        for(char itemType : itemTypes){
           // cout << itemType << endl;
            // STORE SAME ITEMS IN VECTOR
            vector<Item> sameItems;
            for(Item item : items){
                if(item.itemType == itemType){
                    sameItems.push_back(item);
                }
            }
    
            for(int i = 0; i < sameItems.size()-1; i++){
                for(int j = i + 1; j < sameItems.size(); j++){
                    Item firstItem = sameItems[i];
                    Item secondItem = sameItems[j];
                  /*    cout << firstItem.x << firstItem.y << firstItem.itemType << ":";
                    cout << secondItem.x << secondItem.y << secondItem.itemType
                       <<  " " << hasRoute(firstItem.y, firstItem.x, secondItem.y, secondItem.x) <<  endl; */
                    if(hasRoute(firstItem.y, firstItem.x, secondItem.y, secondItem.x))
                        difficulty++;
    
                }
            }
    
        }
    
        return difficulty;
    }
    
    void Game::Board::dispose(){
    
        for(int i = 0; i < height; i++){
            delete[] map[i];
        }
        delete[] map;
    }
    
    Game::Board::~Board(){
    }
    
    Game::Game(){
    
    }
    
    Game::~Game(){
        for(int i = 0; i < boards.size(); i++){
            boards[i].dispose();
        }
    }
    
    void Game::readInput(){
        int tc = 0; // TEST CASE COUNT
    
        cin >> tc;
    
        for(int i = 0; i < tc; i++){
            int w = 0, h = 0; // MAP SIZE
            cin >> h >> w;
            cin.ignore();
            Board board(w, h); // CREATE BOARD
            // READ MAP
            for(int j = 0; j < h; j++){
                string line;
                getline(cin, line);
                for(int k = 0; k < w; k++){
                    if(line.at(k)!='.'){
                        board.setItem(j, k, line.at(k));
                    }
                }
            }
            boards.push_back(board);
    
        }
    
    }
    
    void Game::process(){
        for(Board b : boards){
            cout << b.getDifficulty() << endl;
        }
    }
    
    int main(){
        Game game;
        game.readInput();
        game.process();
    }
    

    제 테스트케이스에요.
    문제없이 작동하던데..

    .........
    ...bb....
    ....sr...
    ..ajk....
    ..a..jk..
    .......o.
    .rhdhmo..
    .sc.c..n.
    ..idinm..
    .t...e.q.
    .l.p.f...
    .....e...
    .p.lqf...
    ...t.....
    .........
    
    .........
    ...bb....
    ..1.sr...
    ..ajk....
    ..a2.jk..
    .......o.
    .rhdhmo..
    .sc3c..n.
    ..idinm..
    .t.4.e.q.
    .l.p.f5..
    .....e...
    .p.lqf6..
    ...t..7..
    .........
    

    8년 전
1개의 댓글이 있습니다.
  • yhw2880
    yhw2880

    후.... 이렇게 막 올려버리시면 보기가 너무 힘드네요 ㅠㅠ
    제 블로그에 올려논 팁 보시면 바로 이해가 가실거같습니다.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.