소프티어

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

const int dx[4] = {-1, 1, 0 ,0};
const int dy[4] = {0, 0, -1, 1};

int bfs(vector<vector<char>>& map, vector<vector<bool>>& visited, pair<int, int> coord, bool can_pass_wall) {
    int rows = map.size();
    int cols = map[0].size();
    queue<pair<pair<int, int>, int>> q; // {{x, y}, move_cnt}

    q.push({coord, 0});
    visited[coord.first][coord.second] = true;

    while(!q.empty()) {
        auto front = q.front();
        q.pop();
        auto cur = front.first;
        int move_cnt = front.second;

        if (map[cur.first][cur.second] == 'D') {
            return move_cnt;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !visited[nx][ny]) {
                if (map[nx][ny] == 'D') {
                    return move_cnt + 1;  // 출구에 도달했으므로, 현재 이동 횟수에 1을 더해 반환
                }
                if (map[nx][ny] == '.' || (map[nx][ny] == '#' && can_pass_wall)) {
                    q.push({{nx, ny}, move_cnt + 1});
                    visited[nx][ny] = true;
                }
            }
        }
    }
    
    return INT_MAX;
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<char>> map(n, vector<char>(m));
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    pair<int, int> namwoo_coord = {-1, -1};
    pair<int, int> ghost1_coord = {-1, -1};
    pair<int, int> ghost2_coord = {-1, -1};
    pair<int, int> exit_coord = {-1, -1};
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'D')
                exit_coord = {i, j};
            else if (map[i][j] == 'N')
                namwoo_coord = {i, j};
            else if (map[i][j] == 'G') {
                if (ghost1_coord.first == -1 && ghost1_coord.second == -1) {
                    ghost1_coord = {i, j};  // 첫 번째 유령의 위치 저장
                } else {
                    ghost2_coord = {i, j};  // 두 번째 유령의 위치 저장
                }
            }
        }
    }

    // ghost1, 2중 에서 출구와 가까운 유령 찾기
    int ghost1 = abs(exit_coord.first - ghost1_coord.first) + abs(exit_coord.second - ghost1_coord.second);
    int ghost2 = INT_MAX;
    if (ghost2_coord.first != -1) {
        ghost2 = abs(exit_coord.first - ghost2_coord.first) + abs(exit_coord.second - ghost2_coord.second);
    }
    bool isG1Closer = ghost1 < ghost2;

    int namwoo_cnt = bfs(map, visited, namwoo_coord, false);
    fill(visited.begin(), visited.end(), vector<bool>(m, false));
    int ghost12_cnt = bfs(map, visited, isG1Closer ? ghost1_coord : ghost2_coord, true);
    
    // cout << namwoo_cnt << endl;
    // cout << ghost12_cnt << endl;
 
    if (namwoo_cnt < ghost12_cnt) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
   return 0;
}