시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB98888.889%

문제

Organic molecules can be amazingly complex and need a great variety of shapes and conventions to represent them, particularly if we wish to depict details of their 3-dimensional structures. However, if we restrict ourselves to reasonably simple compounds, i.e. those with only single bonds between atoms, then we can represent them on a simple rectangular grid with bonds aligned horizontally or vertically. In such a molecule, carbon is bonded to four adjacent atoms, nitrogen to 3, oxygen to 2 and hydrogen to 1. Unfortunately not all such grids represent valid molecules. Your task is to write a program that will determine whether a given grid represents a valid molecule.

입력

Input will consist of a series of possible molecules portrayed as grids. The first line of the input for each molecule will consist of a pair of integers (r and c, 1 ≤ r c ≤ 5) representing the number of rows and columns in the rectangle to follow. The next r lines will contain c characters each, where the characters are chosen from the set {‘.’ (empty), ‘H’ (hydrogen), ‘O’ (oxygen), ‘N’ (nitrogen), ‘C’ (carbon)}. The file will be terminated by a line containing two zeroes (0 0). Note that ‘molecules’ classified as valid may not be physically realisable, and that there may in fact be more than one molecule present.

출력

For each potential molecule in the input, output one of the following lines:

Molecule <num> is valid.
Molecule <num> is invalid.

where <num> is a running number starting at 1.

예제 입력 1

3 4
HOH.
NCOH
OO..
3 4
HOH.
NCOH
OONH
2 3
HOH
HOH
0 0

예제 출력 1

Molecule 1 is valid.
Molecule 2 is invalid.
Molecule 3 is valid.

출처

ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2002 I번

  • 데이터를 추가한 사람: kyo20111