만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

도시와 비트코인

면접 대비

시간 제한1초메모리 제한512 MB

요약
격자의 왼쪽 위에서 오른쪽 아래까지 오른쪽과 아래 방향으로만 이동해 도달할 수 있는지 판별합니다.
난이도

쉬움10점 중 2점

유형
행렬, 동적 계획법
정답자
아직 제출이 없습니다

문제

전날보다 비트코인 시세가 백만 원이나 오른 어느 아침, 진우는 거래소에 가서 비트코인을 팔려고 한다. 시세가 계속 떨어지고 있어서 진우는 최대한 빨리 거래소에 도착해야 한다.

도시는 가로 NN, 세로 MM 크기의 격자로 이루어져 있다. 공터나 도로인 구역은 진우가 지나갈 수 있고, 건물이 있는 구역은 들어갈 수 없다. 진우는 북서쪽 끝에 있고, 거래소는 남동쪽 끝에 있다.

진우는 최대한 빨리 가야 하므로 동쪽(오른쪽) 또는 남쪽(아래쪽)으로만 이동해서 거래소에 도착할 수 있어야 한다. 진우가 거래소에 갈 수 있는지 구하는 프로그램을 작성하라. 진우의 현재 위치가 곧 거래소일 수도 있다.

입력

첫 번째 줄에 도시의 가로 크기 NN과 세로 크기 MM (1≤N,M≤3001 \le N, M \le 300)이 주어진다.

두 번째 줄부터 MM개의 줄에 도시의 형태를 나타내는 NN개의 정수가 공백으로 구분되어 주어진다. 각 칸이 1이면 진우가 갈 수 있는 칸이고, 0이면 갈 수 없는 칸이다.

왼쪽 위 끝 칸과 오른쪽 아래 끝 칸은 모두 1이다.

출력

첫 번째 줄에 진우가 거래소로 갈 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

예제1

  1. 예제 1

    입력
    5 4
    1 1 1 1 1
    0 1 0 0 1
    1 0 0 0 1
    0 0 0 1 1
    
    예상 출력
    Yes