만드는 중입니다

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

숫자 표

면접 대비

시간 제한2초메모리 제한1024 MB

요약
정수 표에서 행이나 열의 부호를 뒤집어 모든 행과 열의 합이 0 이상이 되도록 하는 이동 순서를 찾습니다.
난이도

보통10점 중 5점

유형
행렬, 그리디, 시뮬레이션
정답자
아직 제출이 없습니다

문제

"숫자 표"라는 새로운 1인용 수학 게임에서는 정수로 채워진 nn행 mm열의 표를 사용합니다. 한 번의 이동에서 플레이어는 행 하나 또는 열 하나를 골라, 그 행이나 열에 있는 모든 수의 부호를 반대로 바꿉니다.

게임의 목표는 모든 행의 합과 모든 열의 합이 0 이상인 상태로 표를 만드는 것입니다. 이동 횟수를 최소로 할 필요는 없지만, 이동은 최대 20000번까지 할 수 있습니다.

작성할 프로그램은 초기 표가 주어졌을 때 목표에 도달하는 이동 순서를 찾거나, 목표에 도달할 수 없음을 판별합니다.

입력

첫 줄에 정수 nn과 mm (2≤n,m≤1002 \le n, m \le 100)이 주어집니다. 이어지는 nn개의 줄에는 각각 mm개의 정수 ai,ja_{i,j} (∣ai,j∣≤100|a_{i,j}| \le 100)가 주어집니다.

출력

첫 줄에 이동 횟수 kk를 출력합니다. 목표에 도달할 수 없으면 -1을 출력합니다. 도달할 수 있으면 이어지는 kk개의 줄에 이동을 한 줄에 하나씩 출력합니다. 각 줄에는 이동 종류(행을 고르면 R, 열을 고르면 C)와 그 행 또는 열의 번호를 씁니다. 행과 열은 1부터 번호를 매기며, 행은 위에서 아래로, 열은 왼쪽에서 오른쪽으로 셉니다.

출력하는 이동 순서는 최대 20000번이어야 합니다. 목표에 도달하는 이동 순서가 있다면, 이 제한을 만족하는 순서도 존재함이 보장됩니다.

예제2

  1. 예제 1

    입력
    2 2
    -1 -3
    1 -2
    
    예상 출력
    1
    C 2
    
  2. 예제 2

    입력
    3 2
    -1 -1
    -1 -1
    -1 -1
    
    예상 출력
    3
    R 1
    R 2
    R 3