글 읽기 - 후... 25% 까지 갔다가 틀렷네요

zmfldlwl 7년 전 0

도대체 어디서 틀린걸까요 ... 예외를 못찾겟습니다 ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <stdio.h>
#include <queue>
#include <memory.h>
#include <vector>

using namespace std;

int n, m;
int res_count;

char arr[105][105];
bool visit[105][105];

vector<pair<int, int> > key[30];

int dir_x[4] = { -1, 0, 1, 0 };
int dir_y[4] = { 0, 1, 0, -1 };

void visit_init()
{
    for (int i = 0; i < 105; i++)
    {
        for (int j = 0; j < 105; j++)
        {
            if (arr[i][j] == '.' || arr[i][j] == '$')
                visit[i][j] = 0;
            else if ('a' <= arr[i][j] && arr[i][j] <= 'z')
                visit[i][j] = 0;
            else
                visit[i][j] = 1;
        }
    }
}

int main()
{
    int testcase = 0;
    cin >> testcase;

    for (int test = 0; test < testcase; test++)
    {
        n = 0, m = 0;
        res_count = 0;

        memset(arr, 0, sizeof(arr));
        memset(visit, 0, sizeof(visit));

        for (int i = 0; i < 30; i++)
            key[i].clear();

        for (int i = 0; i < 105; i++) for (int j = 0; j < 105; j++) visit[i][j] = 1;

        cin >> n >> m;

        for (int i = 1; i <= n; i++)
        {
            char temp[105] = { 0, };

            cin >> temp;

            for (int j = 1; j <= m; j++)
            {
                arr[i][j] = temp[j - 1];

                if ('A' <= arr[i][j] && arr[i][j] <= 'Z')
                {
                    key[arr[i][j] - 'A'].push_back(make_pair(i, j));
                }
                else if (arr[i][j] == '.' || ('a' <= arr[i][j] && arr[i][j] <= 'z') || arr[i][j] == '$')
                {
                    visit[i][j] = 0;
                }
                else
                    visit[i][j] = 1;
            }
        }

        char g_key[30] = { 0, };
        cin >> g_key;
        int k = 0;

        while (g_key[k] && g_key[k] != 0)
        {
            //키로 열수있는 문 다 찾아서 열기
            int ll = key[g_key[k] - 'a'].size();

            for (int i = 0; i < ll; i++)
            {
                pair<int, int> temp = key[g_key[k] - 'a'].at(i);
                arr[temp.first][temp.second] = '.';
                visit[temp.first][temp.second] = 0;
            }

            k++;
        }

        //다 열였으면 이제 테두리를 시작점으로 잡음

        queue<pair<int, int> > q2 = queue<pair<int, int> >();

        for (int i = 1; i <= m; i++)
        {
            q2.push(make_pair(1, i));
            q2.push(make_pair(n, i));
        }

        for (int i = 2; i <= n - 1; i++)
        {
            q2.push(make_pair(i, 1));
            q2.push(make_pair(i, m));
        }

        //위 왼 오 아
        while (!q2.empty())
        {
            visit_init();

            pair<int, int> tt = q2.front();
            q2.pop();

            int t_x = tt.first;
            int t_y = tt.second;

            if (((arr[t_x][t_y] == '.' || ('a' <= arr[t_x][t_y] && arr[t_x][t_y] <= 'z')) || arr[t_x][t_y] == '$')
                && !visit[t_x][t_y])
            {
                //탐색 시작
                queue<pair<int, int> > q1 = queue<pair<int, int> >();

                q1.push(make_pair(t_x, t_y));
                visit[t_x][t_y] = 1;

                while (!q1.empty())
                {
                    pair<int, int> temp = q1.front();
                    q1.pop();

                    if ('a' <= arr[temp.first][temp.second] && arr[temp.first][temp.second] <= 'z')
                    {
                        //키를 또 찾앗으면
                        char get_key = arr[temp.first][temp.second];
                        //해당키로 문 다 열고
                        int ll = key[get_key - 'a'].size();

                        for (int i = 0; i < ll; i++)
                        {
                            pair<int, int> temp = key[get_key - 'a'].at(i);
                            arr[temp.first][temp.second] = '.';
                            visit[temp.first][temp.second] = 0;
                        }

                        arr[temp.first][temp.second] = '.';

                        //방문 초기화하고 그 위치에서 다시 시작
                        visit_init();

                        //큐에 다 끄집어내고 현재위치 한개 다시 넣음

                        q1 = queue<pair<int, int> >();

                        q1.push(make_pair(temp.first, temp.second));

                        continue;
                    }

                    if (arr[temp.first][temp.second] == '$')
                    {
                        res_count++;
                        arr[temp.first][temp.second] = '.';
                    }

                    for (int j = 0; j < 4; j++)
                    {
                        if ((arr[temp.first + dir_x[j]][temp.second + dir_y[j]] == '.' || arr[temp.first + dir_x[j]][temp.second + dir_y[j]] == '$' ||
                            ('a' <= arr[temp.first + dir_x[j]][temp.second + dir_y[j]] && arr[temp.first + dir_x[j]][temp.second + dir_y[j]] <= 'z')) &&
                            !visit[temp.first + dir_x[j]][temp.second + dir_y[j]])
                        {
                            q1.push(make_pair(temp.first + dir_x[j], temp.second + dir_y[j]));
                            visit[temp.first + dir_x[j]][temp.second + dir_y[j]] = 1;
                        }
                    }
                }
            }
        }

        cout << res_count << endl;
    }

    return 0;
}

zlzmsrhak 7년 전 0

반례입니다.

1. 85번째 줄에 '0'인 것 같습니다.

2 리셋하는과정에서 입구 처리가 잘못된 것 같습니다.

1
3 4
****
A$*a
****
0

zmfldlwl 7년 전 0

넵 감사합니다. 어제 해보다가 원인찾아서 패스받았어요~~!

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

문제

문제

출처

ICPC

후... 25% 까지 갔다가 틀렷네요

zmfldlwl 7년 전 0

zlzmsrhak 7년 전 0

zmfldlwl 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말