400550: GYM100203 I I WIN
Memory Limit:256 MB
Time Limit:0 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
I. I WINtime limit per test2.0 smemory limit per test256 megabytesinputstandard inputoutputstandard output
Given an n × m rectangular tile with each square marked with one of the letters W, I, and N, find the maximal number of triominoes that can be cut from this tile such that the triomino has W and N on the ends and I in the middle (that is, it spells WIN in some order). Of course the only possible triominoes are the one with three squares in a straight line and the L-shaped ones, and the triominoes can't overlap.
InputFirst line contains two integers n and m with 1 ≤ m, n ≤ 22. The next n lines contain m characters each (only the letters W, I and N).
OutputOutput a single integer: the maximum number of nonoverlapping WIN-triominoes.
ExamplesInput4 4Output
WIIW
NNNN
IINN
WWWI
5Input
5 5Output
NINWN
INIWI
WWWIW
NNNNN
IWINN
5