소프티어

#결국 문제를 쉽게푸는 핵심은 중간에 고스트를 만나서 실패하게될 것을 따지기보단, 결과만을 봤을때 어차피 고스트가 더 거리가 짧다면 이길 수 없는 게임 인것을 인지해야함.

import sys

from collections import deque

#그리고 고스트가 있는경우 고스트의 골인지점 최단거리와 남우 골인지점 최단거리를 비교했을때

#고스트가 민우보다 더 짧은거리면, 민우 패배

#고스트 최단거리는 도착지점(x,y)와 고스트 지점(a,b)를 통해 abs(x-a)+abs(y-b)로 구할수있음.

#민우최단거리는 bfs를 써야함.

def ghost_min_dist(start,end):

  return abs(start[0]-end[0])+abs(start[1]-end[1])

def bfs(grid,start,end):

  row,col=len(grid),len(grid[0])

  visited=set()

  queue=deque([(start[0],start[1],0)])# x , y , 거리 

  directions=[(1,0),(-1,0),(0,1),(0,-1)]

  while(queue):

    x,y,distance=queue.popleft()

    if (x,y) == end:

      return distance

    if (x,y) not in visited:

      visited.add((x,y))

      #print(visited)

      for dx,dy in directions:

        nx=x+dx

        ny=y+dy

        if 0<=nx<row and 0<=ny <col and grid[nx][ny]!='#' and (nx,ny) not in visited:

          queue.append((nx,ny,distance+1))

  return -1

input=sys.stdin.readline

n,m=map(int,input().split(" "))

grid=[]

for i in range(n):

  grid.append(list(input().strip()))

ghost=[]

for i in range(n):

  for j in range(m):

    if grid[i][j]=='.':

      pass

    elif grid[i][j]=='D':

      goal=(i,j)

    elif grid[i][j]=='N':

      namu=(i,j)

    elif grid[i][j]=='G':

      ghost.append((i,j))

#print("goal",goal,"--namu",namu,"--ghost",ghost)

namu_dist=bfs(grid,namu,goal)

ghost_dist=3000

if ghost !=[]:

  for i in ghost:

    ghost_dist=min(ghost_min_dist(i,goal),ghost_dist)

if namu_dist==-1:

  print("No")

else:

  if namu_dist>=ghost_dist:

    print("No")

  else:

    print("Yes")

#print(namu_dist,ghost_dist)