글 읽기 - 3055번 어떤 TC에서 틀렸는지 모르겠습니다. 도와주세요 ㅠㅠ

plzrun 8년 전 2

코드는 길어보이지만, 아주 읽기 쉬워요! 돠주세요 ㅠㅠ

먼저 map을 입력받았구요,

wno가 water number를 의미해요.

그래서 처음 물이 있었던 곳을 1로 초기화 해줬습니다. 나머지는 전부 0으로 초기화가 됩니다.

마찬가지로 map이 S이면 cnt[x][y]배열을 1로 초기화 해줬습니다. 나머지는 전부 0으로 초기화가 됩니다.

그리고 먼저 물을 bfs돌려서 전부 숫자를 채웁니다. map[x][y]=='D'이면 이때만 INT_MAX/2를 넣어주도록 했습니다.

숫자는 하나씩 증가해요 1 옆에 있는 애들의 물 넘버(wno)는 2가되고.. 그 다음은 3이 되고...

cnt도 마찬가지입니다. 처음 1일때를 기준으로 다음 애들을 체크하죠.

그리고 wno값이 cnt보다 크기만 하면 그쪽 map[x][y]으로 고슴도치가 이동할수 있도록 했습니다.

코드 보기 쉽게 하기위해서 한눈에 보실 수 있게 wno[x][y]보여주는 부분과 cnt[x][y]보여주는 부분을 코드에 집어넣었습니다. (주석 풀어주시면 돼용)

왜 틀렸는지 잘 모르겠어요.. ㅠㅠ 테스트 케이스 꽤나 넣어봤는데....

돠주세요 ㅠ

#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
char map[51][51];
int wno[51][51];
int cnt[51][51];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool chk[51][51];
queue<pair<int, int> > wq;
queue<pair<int, int> > q;
int main() {
    int r, c, ex, ey;
    scanf("%d%d ", &r, &c);
    memset(wno, 0, sizeof(wno));
    memset(cnt, 0, sizeof(cnt));
    memset(map, 0, sizeof(map));
    bool hasWater = false;
    for(int i=0; i<r; i++) {
        scanf("%s", map[i]);
        for(int j=0; j<c; j++) {
            if(map[i][j]=='*') {
                hasWater = true;
                wno[i][j] = 1;
                wq.push(make_pair(i, j));
            } else {
                if(map[i][j]=='S') {
                    q.push(make_pair(i, j));
                    cnt[i][j] = 1;
                } else if(map[i][j]=='D') {
                    ex=i;
                    ey=j;
                } else if(map[i][j]=='X') {
                    wno[i][j]=1;
                }
            }
        }
    }
    if(r==1 && c==1) {
        puts("KAKTUS");
        return 0;
    }
    int x, y, nx, ny;
    if(!hasWater) {
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(map[i][j]=='X') continue;
                wno[i][j] = INT_MAX/2;
            }
        }
    } else {
        memset(chk, false, sizeof(chk));
        while(!wq.empty()) {
            x = wq.front().first;
            y = wq.front().second;
            wq.pop();
            for(int i=0; i<4; i++) {
                nx = x + dx[i];
                ny = y + dy[i];
                if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
                if(chk[nx][ny]) continue;
                if(wno[nx][ny]!=0) continue;
                chk[nx][ny] = true;
                if(map[nx][ny]=='D') {
                    wno[nx][ny] = INT_MAX/2;
                    continue;
                } else if(map[nx][ny]=='X') {
                    wno[nx][ny] = 0;
                    continue;
                }
                wno[nx][ny] = wno[x][y]+1;
                wq.push(make_pair(nx, ny));
            }
        }
    }
    /*
       puts("\nmap test");
       for(int i=0; i<r; i++) {
       for(int j=0; j<c; j++) {
       printf("%d ", wno[i][j]);
       }
       puts("");
       }
       */

    memset(chk, false, sizeof(chk));
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
            if(chk[nx][ny]) continue;
            if(cnt[nx][ny]!=0) continue;
            if(wno[nx][ny] <= cnt[x][y]+1) {
                chk[nx][ny] = true;
                continue;
            }
            chk[nx][ny] = true;
            cnt[nx][ny] = cnt[x][y]+1;
            q.push(make_pair(nx, ny));
        }
    }
    /*
       puts("\ncnt test");
       for(int i=0; i<r; i++) {
       for(int j=0; j<c; j++) {
       printf("%d ", cnt[i][j]);
       }
       puts("");
       }
       */
    if(cnt[ex][ey]==0) puts("KAKTUS");
    else printf("%d", cnt[ex][ey]-1);
    return 0;
}

plzrun 8년 전 3

ㅎㅎㅎ 해결했습니다.

10 15
........X......
..XXXXX.X.*....
X.....X.X..*...
.X.S..X.X......
D.X...X.XXXXXXX
.X....X........
.X....X.XXXXXXX
.XXXXXX.X......
........X......
XXXXXXXXX...*..

틀렸던 TC입니다 ㅋㅋ