
71  ZOJ Monthly, October 2008  Snake
"Super Snake" is an old computer game. There are many versions, but all involve maneuvering a "snake" around the screen, trying to avoid running the snake into itself. We'll simulate a very simplified version here. The game will be played on an infinite large board consisting of squares. The snake is initially a string of some connected squares. Connected squares are adjacent horizontally or vertically. In each second, The snake can move to adjacent squares, but will never move back on itself. Thus the only two squares occupied by the snake that change in any move are its head and tail. Note that the head of the snake can't move to the square just vacated by the snake's tail. In a game, started from time 0, a snake of length 2 or more moves for t seconds and does'nt move to itself. Now consider all the squares that have ever been occupied by the snake in these t seconds. You are given the time interval these squares were occupied by the snake, and you will output the coordinates for these squares. Input There are multiple test cases (less than 1000). There are two parts for each case. The first part is one line with two integers N (2 <= N <= 20) and t (1 <= t <= 50), the number of squares that have ever been occupied by the snake in the game and the total time for the game. The second part consists with N lines. Each line consists of t characters. The i_{th} character (0based) is either 'Y' or 'N', represents whether the square is occupied by the snake in time i. Each line contains at least one 'Y' and at least one 'N'. Output For each case, first print "Case i:" where i is the case number (1based) and then N lines each with two integers follow. The i_{th} represent the x and y coordinate for the i_{th} square in the output. All the coordinate you output must by nonnegative and less than 100. If there are more than one possible coordinates set for the squares, you only need to output any one of them. You may assume that there is always at least one solution for each input. Sample Input 7 5 YNNNN YYNNN YYYNN NYYYN NNYYY NNNYY NNNNY 4 5 YNYYY NYYYN YYNYY YYYNY Sample Output Case 1: 0 0 0 1 0 2 0 3 0 4 0 5 0 6 Case 2: 0 1 0 0 1 1 1 0 Author: HANG, Hang 