I have recently downloaded an iPhone app called NumPuzz, developed by Mar- mottajr. I do not read Portugese, but I find this little game quite suitable for our newbies contest. (The app is available for free at the time this problem description is written.) You are given a 3-by-3 square matrix with integer entries that may range from 0 to 9, and your task is to make all the entries zeros. You may click on a square and have that entry, together with its neighbouring entries, decreased by one. If an entry to be reduced is a zero, it becomes a 9 after the click. Of course, you aim at solving the puzzle with the fewest clicks possible. As a simple example, let us suppose that your initial matrix has two zeros in the last two squares, and 1s everywhere else. If you click on the upper right corner, three of the ones turn into zeros. Now it takes just one more click to solve the puzzle. See the illustration below. A player shows you his sequence of clicks to solve a NumPuzz instance (not necessarily optimal). Write a program that returns the initial configuration. Input Input contains no more than 100 lines. Each line gives a string of length not exceeding 200, describing the sequence of the player’s moves. The meanings of the characters are as follows:
2/2 The solution discussed above is described by ‘cd’ (click first on c, then on d). Output For each test case, print the corresponding matrix in the beginning of the game, using the format shown below. Notice that the second line in sample input is empty. It means that no clicks are required to solve that puzzle. Sample Input cd cdifbgah Sample Output Case #1: 111 111 100 Case #2: 000 000 000 Case #3: 333 343 333