글 읽기 - 뭐가 문제인지 모르겠습니다.. 테케랑 다른 반례도 맞습니다.

04_miffy 4년 전 0

무엇이 문제인지 모르겠습니다..

테케랑 질문글에 있는 다른 반례들도 맞는데 바로 틀렸습니다 가 뜹니다. 뭐가 문제일까요...

#include <stdio.h>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <cstring>

using namespace std;

#define MAX_LENGTH 100

struct coor {
    int x;
    int y;
};

char mat[MAX_LENGTH+2][MAX_LENGTH+2];
bool visited[MAX_LENGTH+2][MAX_LENGTH+2];
queue<coor> alphaPath[26];
queue<coor> path;

int tc=0, cnt=0;
int h, w;
int xCoor[4] = {-1, 0, 1, 0};
int yCoor[4] = {0, 1, 0, -1};
string key = "";

void bfs();
void printMat();

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> tc;
    while(tc) {
        tc = tc-1;
        cin >> h >> w;
        
        // init
        //\\ variable
        cnt = 0;
        key = "";
        //\\ array
        for(int i=0; i<h+2; i++) {
            memset(visited[i], false, sizeof(bool)*(w+2));
            memset(mat[i], '.', sizeof(char)*(w+2));
        }
        //\\ queue
        for(int i=0; i<26; i++)
            alphaPath[i] = queue<coor>();
        path = queue<coor>();
        
        
        for(int i=1; i<h+1; i++) {
            for(int j=1; j<w+1; j++) {
                cin >> mat[i][j];
            }
        }
        
        
        cin >> key;
        
        path.push({0, 0});
        visited[0][0] = true;
        
        bfs();
        
        cout << cnt << "\n";
    }
}



void bfs() {
    while(path.size()) {
        for(int i=0; i<path.size(); i++) {
            coor item = path.front(); path.pop();
            int x = item.x; int y = item.y;
            
            // printMat();
            
            // 별다른 조건 없이 그냥 path에 push함
            for(int j=0; j<4; j++) {
                int newX = x + xCoor[j]; int newY = y + yCoor[j];
                
                
                // 여기서 유효성 검사
                if(newX < 0 || newY < 0 || newX > h+1 || newY > w+1) continue;
                
                char value = mat[newX][newY];
                
                // .
                if(value == '.') {
                    // 방문 했었음
                    if(visited[newX][newY]) {
                        continue;
                    }
                    // 방문 안 했었음
                    else {
                        visited[newX][newY] = true;
                        path.push({newX, newY});
                    }
                }
                
                // *
                if(value == '*') {
                    continue;
                }
                // $
                if(value == '$') {
                    cnt = cnt+1;
                    mat[newX][newY] = '.';
                    path.push({newX, newY});
                }
                // 대문자 - 65~90
                if(int(value)>=65 && int(value)<=90) {
                    // key가 있음
                    if(key.find(char(int(value)+32)) != string::npos) {
                        mat[newX][newY] = '.';
                        path.push({newX, newY});
                    }
                    // key가 없음
                    else {
                        int idx = int(value)-65;
                        alphaPath[idx].push({newX, newY});
                    }
                }
                // 소문자 - 97~122
                if(int(value)>=97 && int(value)<=122) {
                    // key가 있었음
                    if(key.find(char(value)) != string::npos) {
                        mat[newX][newY] = '.';
                        path.push({newX, newY});
                    }
                    
                    // key가 없었음
                    else {
                        key.push_back(value);
                        mat[newX][newY] = '.';
                        path.push({newX, newY});
                        
                        int idx = int(value)-97;
                        
                        if(alphaPath[idx].size() > 0) {
                            coor tmp = alphaPath[idx].front(); alphaPath[idx].pop();
                            path.push(tmp);
                        }
                    }
                    
                }
            }
            
        }
    }
}

void printMat() {
    printf("\n");
    for(int i=0; i<h+2; i++) {
        printf("\n");
        for(int j=0; j<w+2; j++) {
            printf("%3c", mat[i][j]);
        }
    }
}

04_miffy 4년 전 4

해결했지만 혹시 저같은 분이 있으실까봐 설명 추가합니다!

저같은 경우는 139~150 에서 맨 앞에 거만 pop해주는게 문제였습니다. 만약 그렇게 되면

4 5

*A***

*$*a.

**$**

**A**

에서 2가 아니라 1이 나오더라구요. 이유는 문이 여러개가 있을 때에 제대로 찾아가지 못해서였습니다. (큐를 만들어놓고도 제대로 쓰지 못하고 있었네요)

이 부분을 고쳐주니 통과했습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

뭐가 문제인지 모르겠습니다.. 테케랑 다른 반례도 맞습니다.

04_miffy 4년 전 0

04_miffy 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말