广度搜索BFS，要用Queue。还不是很熟，这道题帮助理清一些思绪了。其实这道题是求最短路径，所以BFS遇到第一个就可以返回了，所以后面有些现有大小和历史大小的判断可以省却。
过程中拿数组存step还是很有用的。其他的解法中我看到有把四位char编码返回整数的a*26*26*26+b*26*26+c*26+d，很不错，本质就是26进制的数。
import java.util.*;
public class SmartWordToy
{
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() {}
}