Problem Links:
USACO:msquare.
Problem:
Magic Squares
IOI'96
Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares:
In this task we consider the version where each square has a different color. Colors are denoted by the first 8 positive integers. A sheet configuration is given by the sequence of colors obtained by reading the colors of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of
Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration.
Three basic transformations, identified by the letters `A', `B' and `C', can be applied to a sheet:
- 'A': exchange the top and bottom row,
- 'B': single right circular shifting of the rectangle,
- 'C': single clockwise rotation of the middle four squares.
Below is a demonstration of applying the transformations to the initial squares given above:
All possible configurations are available using the three basic transformations.
You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration.
PROGRAM NAME: msquare
INPUT FORMAT
A single line with eight space-separated integers (a permutation of (1..8)) that are the target configuration.
SAMPLE INPUT (file msquare.in)
2 6 8 4 5 7 3 1
OUTPUT FORMAT
| Line 1: | A single integer that is the length of the shortest transformation sequence. |
| Line 2: | The lexically earliest string of transformations expressed as a string of characters, 60 per line except possibly the last line. |
SAMPLE OUTPUT (file msquare.out)
7
BCABCCB
Solution:
This is a shortest path problem. Use BFS + Hash Table to go through every state.
The only problem here is if I use array to store and identify the state, that would exceed time limit. Since we only have 8 digits, we could represent it as an INT.
I think this problem could be solved with DFS using recursion and hash table.
Source Code:
/*
ID: ***
PROB: msquare
LANG: JAVA
*/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
public class msquare {
public static void main(String[] args) throws Exception {
msquare main = new msquare();
main.run();
System.exit(0);
}
private void run() throws Exception {
BufferedReader in = new BufferedReader(new FileReader("msquare.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
"msquare.out")));
String[] strs = in.readLine().split("\\s");
in.close();
// int[] src = { 1, 2, 3, 4, 5, 6, 7, 8 };
int src = 12345678;
int dst = 0;
for (int i = 0; i < 8; i++)
dst = dst * 10 + Integer.parseInt(strs[i]);
Queue<State> queue = new LinkedList<State>();
HashSet<Integer> set = new HashSet<Integer>();
State state = new State(src, "");
queue.add(state);
set.add(state.number);
// System.out.println(state.transformA().number);
// System.out.println(state.transformC().number);
while (queue.isEmpty() == false) {
state = queue.poll();
if (state.number == dst) {
String tmp = state.ops;
out.write(String.format("%d\n%s\n", tmp.length(), tmp));
out.close();
return;
}
State stateA = null;
stateA = state.transformA();
if (set.contains(stateA.number) == false) {
queue.add(stateA);
set.add(stateA.number);
}
stateA = state.transformB();
if (set.contains(stateA.number) == false) {
queue.add(stateA);
set.add(stateA.number);
}
stateA = state.transformC();
if (set.contains(stateA.number) == false) {
queue.add(stateA);
set.add(stateA.number);
}
}
out.close();
}
}
class State implements Comparable<State> {
public int number;
public String ops;
public State(int a, String prev) {
this.number = a;
this.ops = prev;
}
public State transformA() {
int ret = 0;
int cp = number;
for (; cp > 0;) {
int a = cp % 10;
cp /= 10;
ret = ret * 10 + a;
}
String prev = this.ops + "A";
State A = new State(ret, prev);
return A;
}
public State transformB() {
int n = (number / 100000 * 10000)
+ (((number / 10000) % 10) * 10000000) + ((number % 1000) * 10)
+ ((number / 1000) % 10);
String prev = this.ops + "B";
State B = new State(n, prev);
return B;
}
public State transformC() {
int result = 0;
result = number - number % 10000000;
result += (number % 100 - number % 10) * 100000;
result += (number % 10000000 - number % 1000000) / 10;
result += number % 100000 - number % 1000;
result += (number % 1000000 - number % 100000) / 1000;
result += (number % 1000 - number % 100) / 10;
result += number % 10;
String prev = this.ops + "C";
State C = new State(result, prev);
return C;
}
@Override
public int compareTo(State o) {
return this.number - o.number;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
State other = (State) obj;
if (this.number == other.number)
return true;
return false;
}
}
