Problem Links:
Uva12398,Problem:
| Problem B: NumPuzz I |
I have recently downloaded an iPhone app called NumPuzz, developed by Marmottajr. 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:
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: 1 1 1 1 1 1 1 0 0 Case #2: 0 0 0 0 0 0 0 0 0 Case #3: 3 3 3 3 4 3 3 3 3
Solution:
Source Code:
import java.io.BufferedReader;import java.io.InputStreamReader;
/**
* UVa 12398 - NumPuzz I
* Solution:
* Ad-hoc, implementation.
*/
/**
* @author antonio081014
* @since Dec 31, 2011, 3:23:51 PM
*/
public class Main {
public static final int N = 3;
public static final int[] dx = { 0, 1, 0, -1 };
public static final int[] dy = { 1, 0, -1, 0 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String strLine;
for (int t = 1; (strLine = br.readLine()) != null; t++) {
int[][] matrix = new int[N][N];
for (int i = strLine.length() - 1; i >= 0; i--) {
int x = (strLine.charAt(i) - 'a') / 3;
int y = (strLine.charAt(i) - 'a') % 3;
matrix[x][y] = (matrix[x][y] + 1) % 10;
for (int j = 0; j < dx.length; j++) {
int xx = x + dx[j];
int yy = y + dy[j];
if (checkBoundary(xx, yy)) {
matrix[xx][yy] = (matrix[xx][yy] + 1) % 10;
}
}
}
print(t, matrix);
}
}
public static void print(int t, int[][] matrix) {
System.out.println("Case #" + Integer.toString(t) + ":");
for (int i = 0; i < N; i++) {
System.out.print(matrix[i][0]);
for (int j = 1; j < N; j++) {
System.out.print(" ");
System.out.print(matrix[i][j]);
}
System.out.println();
}
}
public static boolean checkBoundary(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N);
}
}
