NYPC 2021 예선 | 페인트 칠하기

[문제]

 

N×M 크기의 격자판이 있다. N 개의 행은 1부터 N까지 번호가 매겨져 있고, M 개의 열은 1부터 M까지 번호가 매겨져 있다.

1부터 7까지 일곱 가지의 색을 격자판에 칠할 수 있다.

색을 칠할 때는 격자판의 한 행을 선택해서 그 행에 있는 모든 격자 칸에 한 색을 덧칠할 수 있고, 혹은 격자판의 한 열을 선택해서 그 열에 있는 모든 격자 칸에 한 색을 덧칠할 수 있다.

예를 들어, 아래와 같이 4×4 크기의 격자판이 있다고 하자. 초기에 각 격자 칸에는 아무런 색이 칠해져 있지 않다.

다음 <그림 1>은 3 번 행에 빨간색(1번 색)을 칠하고 3 번 열에 파란색(3번 색)을 칠했을 때의 과정을 보여준다.

<그림 1> 격자판에 색을 칠하는 과정

각 격자 칸마다 최종적으로 칠해져 있는 색이 주어질 때, 적절히 색을 칠해 주어진 상황이 되도록 하자.

 

 

[입력 형식]

 

첫 줄에 격자판의 크기를 나타내는 두 정수 N과 M이 공백으로 구분되어 주어진다. (1≤N,M≤100)

그 다음 N 개의 줄에 각 격자 칸마다 최종적으로 칠해져 있는 색을 나타내는 M 개의 수가 공백으로 구분되어 주어진다.

주어지는 수는 0 이상 7 이하이며, 주어지는 수가 0인 경우 색이 칠해져 있지 않거나 어떠한 색이 칠해져 있어도 상관 없음을 의미한다.

적절히 색을 칠해 주어진 상황을 항상 만들 수 있는 입력이 주어진다.

 

 

[출력 형식]

 

첫 줄에 색을 칠하는 횟수 K를 출력한다. 출력하는 K는 10000보다 크지 않아야 한다.

그 다음 K 개의 줄에 걸쳐, 각 줄에 색칠하는 연산을 나타내는 한 개의 문자와 두 개의 정수를 색칠 순서대로 출력한다.

행을 선택하여 색칠하는 경우 H 행번호 색번호 형식으로 출력하고, 열을 선택하여 색칠하는 경우 V 열번호 색번호 형식으로 출력한다.

색을 칠하는 횟수 K를 가장 작게 할 필요는 없다.

만약, 가능한 답이 여러 가지인 경우 그중 아무거나 하나 출력한다.

 

 

[해설]

 

마지막에 칠한 행/열은 모두 색이 동일합니다.

그러므로 행/열의 색이 동일한 경우에는 이를 지워주면서 문제를 해결해주면 됩니다.

 

 

[C/C++ 코드]

 

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
struct st{
    char x;
    int y,z;
    st(){}
    st(char _x, int _y, int _z): x(_x), y(_y), z(_z){}
};
int arr[101][101];
vector<st>ans;

bool flag(int n,int m){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
        	if(arr[i][j]){
        		return 0;
			}
		}
    }
    return 1;
}

void color(int n,int m){
    for(int i=0;i<n;i++){
        int cur=0;
        for(int j=0;j<m;j++){
            if(!cur&&arr[i][j]){
            	cur=arr[i][j];
			}
            else if(arr[i][j]&&cur!=arr[i][j]){
            	cur=-1;
			}
        }
        if(cur>0){
            ans.emplace_back('H',i+1,cur);
            for(int j=0;j<m;j++){
            	arr[i][j]=0;
			}
            return;
        }
    }
    for(int j=0;j<m;j++){
        int cur=0;
        for(int i=0;i<n;i++){
            if(!cur&&arr[i][j]){
            	cur=arr[i][j];
			}
            else if(arr[i][j]&&cur!=arr[i][j]){
            	cur=-1;
			}
        }
        if(cur>0){
            ans.emplace_back('V',j+1,cur);
            for(int i=0;i<n;i++){
            	arr[i][j]=0;
			}
            return;
        }
    }
    exit(1);
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
        	cin>>arr[i][j];
		}
    }
    while(!flag(n,m)){
    	color(n,m);
	}
    cout<<ans.size()<<'\n';
    reverse(ans.begin(), ans.end());
    for(auto &i:ans){
    	cout<<i.x<<" "<<i.y<<" "<<i.z<<'\n';
	}
}