algospot.com :: 질문과 답변: SHISENSHO 도움 부탁 드려요..

SHISENSHO 도움 부탁 드려요..

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

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

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

제가 설정한 케이스는요:
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

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

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

SINCE 2007

다가오는 이벤트들

SHISENSHO 도움 부탁 드려요..

1개의 댓글이 있습니다.