Third Avenue Editorial(AtCoder Beginner Contest 184, E)

문제 위치 E - Third Avenue

본인 작성 코드

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define ll  long long
#define INF 987654321
#define pa pair<int,int>
using namespace std;
vector<vector<char>> mapp;
vector<vector<int>> dist;
int dirX[] = {1,0,-1,0};
int dirY[] = {0,1,0,-1};
int h, w;

void bfs(int y, int x) {

    queue<pa> q;
    q.push({ y, x });
    while (!q.empty()) {

        pa po = q.front(); q.pop();
        if (mapp[po.first][po.second] == 'G')
            break;

        for (int dir = 0; dir < 4; ++dir) {
            int nextY = po.first + dirY[dir];
            int nextX = po.second + dirX[dir];
            if (nextY < 0 || nextX < 0 || nextY >= h || nextX >= w ||mapp[nextY][nextX]=='#'|| dist[nextY][nextX] < INF) {
                continue;
            }
            dist[nextY][nextX] = dist[po.first][po.second] + 1;
            q.push({ nextY, nextX });            
        }

        if ((int)mapp[po.first][po.second] >= (int)'a' && (int)mapp[po.first][po.second] <= (int)'z') {
            int nextY=-1, nextX=-1;
            for(int y=0;y<h;y++)
                for (int x = 0; x < w; x++) {
                    if (mapp[po.first][po.second] == mapp[y][x] && !(po.first == y && po.second == x))
                        nextY = y, nextX = x;
                }
            if (nextY != -1 && nextX != -1&& dist[nextY][nextX] == INF) {

                dist[nextY][nextX] = dist[po.first][po.second] + 1;
                q.push({ nextY, nextX });
            }
        }
    }
}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

     cin >> h >> w;
    mapp = vector<vector<char>>(h, vector<char>(w));
    dist = vector<vector<int>>(h, vector<int>(w,INF));
    pa start,end;
    for (int y = 0; y < h; y++)
        for (int x = 0; x < w; x++) {
            cin >> mapp[y][x];
            if (mapp[y][x] == 'S') {
                start = { y,x };
                dist[y][x] = 0;
            }
            else if (mapp[y][x] == 'G')
                end = { y,x };
        }

    bfs(start.first, start.second);
    if (dist[end.first][end.second] == INF)
        cout << -1 << endl;
    else
        cout << dist[end.first][end.second] << endl;



    return 0;
}

개선 요구 사항

• edge 케이스에서 실패함
• 일일히 검사하는 것이 아니라, 알파벳으로 이루어진 위치의 경우 저장을 개선하면 시간을 줄일 수 있을 것으로 보임