5398번 - 틀렸습니다 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 607 | 255 | 194 | 42.358% |
문제
승혁이는 크로스워드 퍼즐을 풀고 있었다. 승혁이는 크로스워드의 개고수다. 그런데 퍼즐을 다 풀고 단어를 적어 넣으려니 서로 위치가 겹치면서 글자가 다른, 즉 틀린 경우가 발생하고 말았다. 승혁이는 답을 고치는 것 대신에 지금 알아낸 답들이 서로 충돌하지 않게 하면서 최대한 많이 배치하는 걸 하려고 한다.
현재 승혁이가 답이라 생각하는 단어들을 정해진 위치에 배치하면서, 서로 충돌하는 경우가 하나도 없게 하면서 배치할 수 있는 단어 개수는 최대 몇 개일까?
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
- 첫째 줄에 각각 가로 단어, 세로 단어 개수를 의미하는 두 정수 H, V가 주어진다. (1 ≤ H, V ≤ 500)
- 이어서 H개 줄에 각 가로 단어의 시작 위치 x, y, 그리고 승혁이가 답이라고 생각하는 단어 W가 주어진다. (0 ≤ x, y ≤ 1,000 이고 1 ≤ Length(W) ≤ 1,000)
- 이어서 V개 줄에 각 세로 단어의 시작 위치 x, y, 그리고 승혁이가 답이라고 생각하는 단어 W가 주어진다. (0 ≤ x, y ≤ 1,000 이고 1 ≤ Length(W) ≤ 1,000)
모든 단어는 알파벳 대문자로만 이루어져 있으며, 가로 단어끼리 위치가 겹치거나 세로 단어끼리 위치가 겹치는 경우는 없다.
퍼즐판의 제일 왼쪽 위 칸은 x = y = 0이다. x는 가로 위치, y는 세로 위치를 결정한다. 또한 가로 단어는 오른쪽 방향으로, 세로 단어는 아래 방향으로 써내려져 간다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 정답을 출력한다.
예제 입력 1
2 2 2 0 1 BAPC 0 2 LEIDEN 0 0 SOLUTION 2 1 WINNER 1 4 0 1 HELLO 1 0 HI 2 0 BYE 3 0 GOODBYE 4 0 FAREWELL
예제 출력 1
3 4
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2010 J번
- 문제를 번역한 사람: kks227
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호