[백준 6087] 레이저 통신, C++

https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

 본 문제는 Olympiad 2008-2009 Season January 2009 Contest Silver 3번 문제다. 지도에 빈칸과 벽 그리고 레이저 2개가 있다. 이 두 개의 레이저로 통신을 하기 위해 거울을 설치하려고 한다. 설치하려는 거울의 최소 개수를 구하여라. (단, 거울은 90도 회전만 시킬 수 있다.) BFS로 풀었으며, 문제 해결 과정은

1. 범위 안에서 벽이 나올 때까지 계속 이동한다.
2. (이동한 횟수) - 1 = (거울의 개수) 다.

#include <iostream>
#include <queue>
#include <vector>
#include <string>
 
using namespace std;
 
int d[101][101];
char map[101][101];
bool chk[101][101];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
int main() {
    int n, m;
    cin >> m >> n;
    cin.ignore();
    string s;
    vector<pair<int, int>> c;
    for (int i = 0; i < n; i++) {
        getline(cin, s);
        for (int j = 0; j < s.size(); j++) {
            map[i][j] = s[j];
            if (map[i][j] == 'C') {
                c.push_back(make_pair(i, j));
            }
        }
    }
    int s1 = c[0].first;
    int s2 = c[0].second;
    queue<pair<int, int>> q;
    q.push(make_pair(s1, s2));
    d[s1][s2] = 0;
    chk[s1][s2] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            while (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (map[nx][ny] == '*') break;
                if (!chk[nx][ny]) {
                    chk[nx][ny] = true;
                    d[nx][ny] = d[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
                nx += dx[k];
                ny += dy[k];
            }
        }
    }
    cout << d[c[1].first][c[1].second] -1 << "\n";
}