https://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532
http://code.antonio081014.com/2014/03/topcoder-srm-233-div1-level2.html
https://github.com/irpap/TopCoder/blob/master/SmartWordToy/src/SmartWordToy.java
public int minPresses(String start, String finish, String[] forbid) {
Node.initForbidden(forbid);
Node s = new Node(start.toCharArray());
// System.out.println(s.neighbors());
return bfs(s, finish);
}
private int bfs(Node s, String finish) {
HashSet<String> visited = new HashSet<String>();
LinkedList<Node> q = new LinkedList<Node>();
q.add(s);
while (q.isEmpty() == false) {
Node top = q.getFirst();
q.removeFirst();
// System.out.println(top);
visited.add(top.toString());
if (top.toString().equals(finish)) return top.steps;
for (Node neighbor : top.neighbors()) {
if (!visited.contains(neighbor.toString())) {
neighbor.steps = top.steps + 1;
q.add(neighbor);
}
}
}
return -1;
}
static class Node {
public static final char A = 'a';
int steps = 0;
static boolean[][][][] forbidden;
private static void initForbidden(final String[] forbid) {
boolean[][][][] forbidden = new boolean[26][26][26][26];
for (String s : forbid) {
String[] split = s.split(" ");
for (int i = 0; i < split[0].length(); i++) {
for (int j = 0; j < split[1].length(); j++) {
for (int k = 0; k < split[2].length(); k++) {
for (int l = 0; l < split[3].length(); l++) {
forbidden[split[0].charAt(i) - A][split[1].charAt(j) - A][split[2].charAt(k) - A][split[3].charAt(l) - A] = true;
}
}
}
}
}
Node.forbidden = forbidden;
}
Node(char[] word) {
this.word = word;
}
char[] word = new char[4];
public String toString() {
return new String(word);
}
List<Node> neighbors() {
HashSet<Node> neighbors = new HashSet<Node>();
for (int i = 0; i < word.length; i++) {
char[] prev = createWordWithNextLetter(i);
addToNeighborsIfNotForbidden(neighbors, prev);
}
for (int i = 0; i < word.length; i++) {
char[] next = createWordWithPrevLetter(i);
addToNeighborsIfNotForbidden(neighbors, next);
}
return new LinkedList(neighbors);
}
private void addToNeighborsIfNotForbidden(HashSet<Node> neighbors, char[] next) {
if (isForbidden(next) == false) {
neighbors.add(new Node(next));
}
}
private char[] createWordWithPrevLetter(int i) {
char[] next = new char[4];
for (int j = 0; j < word.length; j++) {
next[j] = (i == j) ? next(word[j]) : word[j];
}
return next;
}
private char[] createWordWithNextLetter(int i) {
char[] prev = new char[4];
for (int j = 0; j < word.length; j++) {
prev[j] = (i == j) ? prev(word[j]) : word[j];
}
return prev;
}
private boolean isForbidden(char[] word) {
return forbidden[word[0] - A][word[1] - A][word[2] - A][word[3] - A];
}
private char next(char c) {
if (c == 'z') return 'a';
return (char) (c + 1);
}
private char prev(char c) {
if (c == 'a') return 'z';
return (char) (c - 1);
}
}
https://code.google.com/p/my-topcoder/source/browse/trunk/topcoder/SmartWordToy.java?spec=svn11&r=11
https://github.com/irpap/TopCoder/blob/master/SmartWordToy/src/SmartWordToy.java
https://github.com/ahmed-fathy-aly/TopCoder/blob/master/smartwordtoy-java/SmartWordToy.java
|
* For this problem, it's easy to find out each 4-digit string is a state. And * it's easy to move to next state from current state by going to next * alpha-letter or previous alpha-letter. So here, using BFS to track the state * to state process, and find out the shortest distance from start to finish * state. * * PS: initially, I used Map interface to keep the record of state's distance * from start, it will Exceed Time Limit. Then, I used a 4-dim array to keep * track of the state's distance. It works like a charm now. I think it's the * getter of Map interface costs too much time since I instantized with a * linkedlist, each time the iterator will go through every element in the map * to check the value of the key. // Map<String, Integer> map; int[][][][] count; public int minPresses(String start, String finish, String[] forbid) { // map = new HashMap<String, Integer>(); count = new int[26][26][26][26]; // map.put(start, 0); for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) for (int m = 0; m < 26; m++) for (int n = 0; n < 26; n++) count[i][j][m][n] = -1; preprocess(forbid); setCounter(start, 0); Queue<String> q = new LinkedList<String>(); q.add(start); while (!q.isEmpty()) { start = q.poll(); if (start.compareTo(finish) == 0) return getCounter(start); int value = getCounter(start); for (int i = 0; i < 4; i++) { String next = nextString(start, i); if (getCounter(next) == -1) { setCounter(next, value + 1); // map.put(next, map.get(start) + 1); q.add(next); } String prev = prevString(start, i); if (getCounter(prev) == -1) { setCounter(prev, value + 1); q.add(prev); } } } return -1; } private void setCounter(String s, int value) { count[s.charAt(0) - 'a'][s.charAt(1) - 'a'][s.charAt(2) - 'a'][s .charAt(3) - 'a'] = value; } private int getCounter(String s) { return count[s.charAt(0) - 'a'][s.charAt(1) - 'a'][s.charAt(2) - 'a'][s .charAt(3) - 'a']; } private void preprocess(String[] forbid) { for (String s : forbid) { String[] str = s.split("\\s"); for (int i = 0; i < str[0].length(); i++) { for (int j = 0; j < str[1].length(); j++) { for (int m = 0; m < str[2].length(); m++) { for (int n = 0; n < str[3].length(); n++) { // String tmp = "" + str[0].charAt(i) // + str[1].charAt(j) + str[2].charAt(m) // + str[3].charAt(n); // map.put(tmp, -1); count[str[0].charAt(i) - 'a'][str[1].charAt(j) - 'a'][str[2] .charAt(m) - 'a'][str[3].charAt(n) - 'a'] = -10; } } } } } } private String nextString(String s, int index) { return s.substring(0, index) + (char) ('a' + (s.charAt(index) - 'a' + 1) % 26) + s.substring(index + 1); } private String prevString(String s, int index) { return s.substring(0, index) + (char) ('a' + (s.charAt(index) - 'a' + 25) % 26) + s.substring(index + 1); }http://www.cnblogs.com/lautsie/p/3263700.html
广度搜索BFS,要用Queue。还不是很熟,这道题帮助理清一些思绪了。其实这道题是求最短路径,所以BFS遇到第一个就可以返回了,所以后面有些现有大小和历史大小的判断可以省却。
过程中拿数组存step还是很有用的。其他的解法中我看到有把四位char编码返回整数的a*26*26*26+b*26*26+c*26+d,很不错,本质就是26进制的数。
public
int
minPresses(String start, String finish, String[] forbid) {
int
[][][][] step =
new
int
[
26
][
26
][
26
][
26
];
int
[][][][] forb =
new
int
[
26
][
26
][
26
][
26
];
for
(
int
a =
0
; a <
26
; a++)
for
(
int
b =
0
; b <
26
; b++)
for
(
int
c =
0
; c <
26
; c++)
for
(
int
d =
0
; d <
26
; d++)
{
step[a][b][c][d] = -
1
;
forb[a][b][c][d] =
0
;
}
for
(
int
i =
0
; i < forbid.length; i++) {
String[] lines = forbid[i].split(
" "
);
for
(
int
a =
0
; a < lines[
0
].length(); a++) {
for
(
int
b =
0
; b < lines[
1
].length(); b++) {
for
(
int
c =
0
; c < lines[
2
].length(); c++) {
for
(
int
d =
0
; d < lines[
3
].length(); d++) {
forb[lines[
0
].charAt(a)-
'a'
][lines[
1
].charAt(b)-
'a'
][lines[
2
].charAt(c)-
'a'
][lines[
3
].charAt(d)-
'a'
] =
1
;
}
}
}
}
}
LinkedList<Word> queue =
new
LinkedList<Word>();
Word sw =
new
Word(start.charAt(
0
), start.charAt(
1
), start.charAt(
2
), start.charAt(
3
));
step[sw.a-
'a'
][sw.b-
'a'
][sw.c-
'a'
][sw.d-
'a'
] =
0
;
queue.offer(sw);
Word fw =
new
Word(finish.charAt(
0
), finish.charAt(
1
), finish.charAt(
2
), finish.charAt(
3
));
while
(queue.size() !=
0
) {
Word w = queue.poll();
int
cur_step = step[w.a-
'a'
][w.b-
'a'
][w.c-
'a'
][w.d-
'a'
];
if
(w.a == fw.a && w.b == fw.b && w.c == fw.c && w.d == fw.d)
return
cur_step;
Word tmp =
new
Word();
tmp.a = next(w.a); tmp.b = w.b; tmp.c = w.c; tmp.d = w.d;
int
tmp_step = step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
];
if
(forb[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] ==
0
&& (tmp_step == -
1
|| tmp_step > cur_step+
1
)) {
step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] = cur_step +
1
;
queue.offer(tmp);
}
tmp =
new
Word();
tmp.a = prev(w.a); tmp.b = w.b; tmp.c = w.c; tmp.d = w.d;
tmp_step = step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
];
if
(forb[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] ==
0
&& (tmp_step == -
1
|| tmp_step > cur_step+
1
)) {
step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] = cur_step +
1
;
queue.offer(tmp);
}
tmp =
new
Word();
tmp.a = w.a; tmp.b = next(w.b); tmp.c = w.c; tmp.d = w.d;
tmp_step = step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
];
if
(forb[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] ==
0
&& (tmp_step == -
1
|| tmp_step > cur_step+
1
)) {
step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] = cur_step +
1
;
queue.offer(tmp);
}
tmp =
new
Word();
tmp.a = w.a; tmp.b = prev(w.b); tmp.c = w.c; tmp.d = w.d;
tmp_step = step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
];
if
(forb[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] ==
0
&& (tmp_step == -
1
|| tmp_step > cur_step+
1
)) {
step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] = cur_step +
1
;
queue.offer(tmp);
}
tmp =
new
Word();
tmp.a = w.a; tmp.b = w.b; tmp.c = next(w.c); tmp.d = w.d;
tmp_step = step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
];
if
(forb[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] ==
0
&& (tmp_step == -
1
|| tmp_step > cur_step+
1
)) {
step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] = cur_step +
1
;
queue.offer(tmp);
}
tmp =
new
Word();
tmp.a = w.a; tmp.b = w.b; tmp.c = prev(w.c); tmp.d = w.d;
tmp_step = step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
];
if
(forb[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] ==
0
&& (tmp_step == -
1
|| tmp_step > cur_step+
1
)) {
step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] = cur_step +
1
;
queue.offer(tmp);
}
tmp =
new
Word();
tmp.a = w.a; tmp.b = w.b; tmp.c = w.c; tmp.d = next(w.d);
tmp_step = step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
];
if
(forb[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] ==
0
&& (tmp_step == -
1
|| tmp_step > cur_step+
1
)) {
step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] = cur_step +
1
;
queue.offer(tmp);
}
tmp =
new
Word();
tmp.a = w.a; tmp.b = w.b; tmp.c = w.c; tmp.d = prev(w.d);
tmp_step = step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
];
if
(forb[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] ==
0
&& (tmp_step == -
1
|| tmp_step > cur_step+
1
)) {
step[tmp.a-
'a'
][tmp.b-
'a'
][tmp.c-
'a'
][tmp.d-
'a'
] = cur_step +
1
;
queue.offer(tmp);
}
}
return
step[finish.charAt(
0
)-
'a'
][finish.charAt(
1
)-
'a'
][finish.charAt(
2
)-
'a'
][finish.charAt(
3
)-
'a'
];
}
private
char
next(
char
c) {
if
(c ==
'z'
)
return
'a'
;
else
return
(
char
)(c+
1
);
}
private
char
prev(
char
c) {
if
(c ==
'a'
)
return
'z'
;
else
return
(
char
)(c-
1
);
}
}
class
Word
{
char
a;
char
b;
char
c;
char
d;
public
Word(
char
_a,
char
_b,
char
_c,
char
_d) {
a = _a; b = _b; c = _c; d = _d;
}
public
Word() {}
}
public int minPresses(String start, String finish, String[] forbid) {
Node.initForbidden(forbid);
Node s = new Node(start.toCharArray());
// System.out.println(s.neighbors());
return bfs(s, finish);
}
private int bfs(Node s, String finish) {
HashSet<String> visited = new HashSet<String>();
LinkedList<Node> q = new LinkedList<Node>();
q.add(s);
while (q.isEmpty() == false) {
Node top = q.getFirst();
q.removeFirst();
// System.out.println(top);
visited.add(top.toString());
if (top.toString().equals(finish)) return top.steps;
for (Node neighbor : top.neighbors()) {
if (!visited.contains(neighbor.toString())) {
neighbor.steps = top.steps + 1;
q.add(neighbor);
}
}
}
return -1;
}
static class Node {
public static final char A = 'a';
int steps = 0;
static boolean[][][][] forbidden;
private static void initForbidden(final String[] forbid) {
boolean[][][][] forbidden = new boolean[26][26][26][26];
for (String s : forbid) {
String[] split = s.split(" ");
for (int i = 0; i < split[0].length(); i++) {
for (int j = 0; j < split[1].length(); j++) {
for (int k = 0; k < split[2].length(); k++) {
for (int l = 0; l < split[3].length(); l++) {
forbidden[split[0].charAt(i) - A][split[1].charAt(j) - A][split[2].charAt(k) - A][split[3].charAt(l) - A] = true;
}
}
}
}
}
Node.forbidden = forbidden;
}
Node(char[] word) {
this.word = word;
}
char[] word = new char[4];
public String toString() {
return new String(word);
}
List<Node> neighbors() {
HashSet<Node> neighbors = new HashSet<Node>();
for (int i = 0; i < word.length; i++) {
char[] prev = createWordWithNextLetter(i);
addToNeighborsIfNotForbidden(neighbors, prev);
}
for (int i = 0; i < word.length; i++) {
char[] next = createWordWithPrevLetter(i);
addToNeighborsIfNotForbidden(neighbors, next);
}
return new LinkedList(neighbors);
}
private void addToNeighborsIfNotForbidden(HashSet<Node> neighbors, char[] next) {
if (isForbidden(next) == false) {
neighbors.add(new Node(next));
}
}
private char[] createWordWithPrevLetter(int i) {
char[] next = new char[4];
for (int j = 0; j < word.length; j++) {
next[j] = (i == j) ? next(word[j]) : word[j];
}
return next;
}
private char[] createWordWithNextLetter(int i) {
char[] prev = new char[4];
for (int j = 0; j < word.length; j++) {
prev[j] = (i == j) ? prev(word[j]) : word[j];
}
return prev;
}
private boolean isForbidden(char[] word) {
return forbidden[word[0] - A][word[1] - A][word[2] - A][word[3] - A];
}
private char next(char c) {
if (c == 'z') return 'a';
return (char) (c + 1);
}
private char prev(char c) {
if (c == 'a') return 'z';
return (char) (c - 1);
}
}
https://code.google.com/p/my-topcoder/source/browse/trunk/topcoder/SmartWordToy.java?spec=svn11&r=11
https://github.com/irpap/TopCoder/blob/master/SmartWordToy/src/SmartWordToy.java
https://github.com/ahmed-fathy-aly/TopCoder/blob/master/smartwordtoy-java/SmartWordToy.java