만드는 중입니다

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

별 가두기

면접 대비

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

요약
각 칸의 숫자만큼 별이 오른쪽, 아래, 왼쪽, 위 순서로 방향을 바꾸며 움직일 때 격자를 벗어나지 않는 1열 시작 칸을 찾습니다.
난이도

보통10점 중 4점

유형
시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

스타는 별을 가두는 장치를 만들어 본인이 가진 별을 보관하려고 한다.

스타의 장치에는 N×MN \times M 크기의 격자가 있으며, 격자의 각 칸에는 양의 정수가 적혀 있다. 장치는 다음 과정으로 격자에 별을 가둔다.

  1. 첫 번째 열의 원하는 칸에 별을 올려 둔다.
  2. 별이 다음 과정을 따라 이동한다.
    1. 별은 바라보고 있는 방향으로, 별이 놓인 칸에 적힌 수만큼 이동한다.
    2. 별이 바라보는 방향이 시계 방향으로 90도 돌아간다.

별은 처음에 오른쪽을 바라보고 있다. 별이 격자 밖으로 나가지 않고 위 과정이 무한히 반복되면 별을 성공적으로 가둔 것이다. 중간에 별이 격자 밖으로 나가면 별을 가두는 데 실패한 것이다.

스타는 처음에 별을 어느 칸에 올려야 가둘 수 있는지 알고 싶다. 별을 가둘 수 있는 칸을 구해 보자.

입력

첫째 줄에 장치의 세로 길이 NN과 가로 길이 MM이 주어진다. NN, MM은 정수이다. (1≤N≤1001 \leq N \leq 100, 1≤M≤1001 \leq M \leq 100)

둘째 줄부터 NN개의 줄에 걸쳐 격자에 적힌 값이 공백을 사이에 두고 주어진다. 격자에 적힌 값은 11 이상 min⁡(N,M)\min(N, M) 이하의 정수이다.

출력

첫째 줄에는 별을 가두기 위해 처음에 올려 둘 수 있는 칸의 개수를 출력한다.

둘째 줄에는 그런 칸이 몇 번째 행에 있는지 공백을 사이에 두고 오름차순으로 출력한다. 그런 칸이 없으면 둘째 줄은 출력하지 않는다.

예제3

  1. 예제 1

    입력
    4 4
    1 2 2 3
    2 2 1 1
    3 2 1 2
    1 2 2 2
    
    예상 출력
    1
    2
    
  2. 예제 2

    입력
    6 5
    3 1 1 2 1
    4 2 1 3 1
    4 1 1 3 3
    4 3 3 1 2
    5 1 1 2 2
    3 2 3 3 3
    
    예상 출력
    3
    2 3 4
    
  3. 예제 3

    입력
    5 6
    5 2 3 3 1 1
    4 2 2 1 1 3
    3 1 2 2 1 3
    5 3 2 1 1 2
    3 2 3 3 3 2
    
    예상 출력
    0