Powering Teslopolis

면접 대비

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

요약
건물과 ERT로 이루어진 N×M 격자가 주어질 때, 모든 건물이 여덟 방향으로 인접한 칸 중 하나에 ERT를 두고 있는지 확인하고, 전력이 공급되지 않는 건물의 좌표를 행 우선 순서로 출력한다.
난이도

쉬움10점 중 3점

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

문제

The city of Teslopolis is an interesting city, to say the least. Due to its location at the peak of the Stormlight Mountains, the entire city is always encompassed by storms, and its residents have invented an ingenious method of harnessing the perpetual lightning to power the city: electrical resonant transformers (ERT's).

The ERT's are placed at strategic locations throughout Teslopolis and act as both lightning rods and electrical generators that attract, ground, and harness the lightning's energy. Each ERT is connected to and powers all adjacent buildings (including diagonally adjacent). However, the city currently has no method for rapidly determining if all buildings would be powered given the layout of a new subdivision. As an intern for the city's current administration, your boss has instructed you to write an algorithm that determines, given the layout of a planned subdivision, if all buildings are powered.

입력

The first line of input is the number of rows in the planned subdivision, 1≤N≤301 \leq N \leq 30, followed by the number of columns in the planned subdivision, 1≤M≤301 \leq M \leq 30. Following the first two lines are NN lines of exactly MM buildings (represented by a "b") or ERT's (represented by a "T").

출력

Output "True" if all buildings are powered. Output "False" if any building is not powered.

If not all buildings are powered, output in numerical order the row and column index location of each unpowered building. Numerical ordering means you should sort first by the xx values and then by the yy values. For example, if none of the locations are powered, you would print 0 0 followed by 0 1, 0 2, etc. until you reach the last row. Then, you would print 1 0, 1 1, etc. to repeat the pattern for all of the rows.

예제2

  1. 예제 1

    입력
    3
    3
    bbb
    bTb
    bbb
    
    예상 출력
    True
    
  2. 예제 2

    입력
    4
    3
    bbT
    Tbb
    bbb
    Tbb
    
    예상 출력
    False
    2 2
    3 2