2
私は以下のコードを試しましたが、それは私に正しい答えを与えませんでした。鍵と扉を持つパズルの最短経路を見つける方法
ここに問題文があります。
2-Dグリッドがあるとします。各ポイントは土地または水のいずれかです。そこには も出発点と目標です。
ドアを開くキーがあります。各キーは1つの ドアに対応しています。
土地のタイル、キー、ドアを使用して目標から までの最短経路を返す関数を実装します。
データ表現
マップは文字列の配列として渡されます。
マップには次のタイルを配置できます。
0 = Water1 = Land2 = Start3 = Goaluppercase = doorlowercase = keyグリッドは次のようにすることができる：
{{'0', '2', '1', '1', '1'}, {'0', '1', '0', '0', '1'}, {'0', '0', '0', '0', '1'}, {'0', '0', 'A', '0', '1'}, {'1', '1', 'a', '1', '1'}, {'1', 'b', '0', '0', 'B'}, {'1', '1', '0', '0', '1'}, {'0', '1', '0', '0', '3'}};だから最短経路があるべき： 01-> 02-> 03-> 04-> 14 →24→34→44→43→42→41→51→41→42→43→44→54→64→74
そして、私のコードは次のように行く：
public class shortestPath {
static int shortest = Integer.MAX_VALUE;
static String path = "";
static ArrayList<ArrayList<int[]>> res = new ArrayList<ArrayList<int[]>>();
public static void main(String[] args) {
char[][] board = {{'0', '2', '1', '1', '1'},
{'0', '1', '0', '0', '1'},
{'0', '0', '0', '0', '1'},
{'0', '0', 'A', '0', '1'},
{'1', '1', 'a', '1', '1'},
{'1', 'b', '0', '0', 'B'},
{'1', '1', '0', '0', '1'},
{'0', '1', '0', '0', '3'}};
System.out.println(findShortest(board));
System.out.println(path);
}
public static int findShortest(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) return 0;
int row = board.length;
int col = board[0].length;
int[] start = new int[2];
int[] end = new int[2];
int[][] visited = new int[row][col];
HashMap<Character, ArrayList<int[]>> hm = new HashMap<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == '2') {
start = new int[]{i, j};
}
if (board[i][j] == '3') {
end = new int[]{i, j};
}
if (Character.isUpperCase(board[i][j])) {
char key = Character.toLowerCase(board[i][j]);
if (hm.containsKey(key)) {
hm.get(key).add(new int[]{i, j});
} else {
ArrayList<int[]> al = new ArrayList<>();
al.add(new int[]{i, j});
hm.put(key, al);
}
board[i][j] = '0';
}
}
}
//HashSet<Character> hs = new HashSet<Character>();
//helper2(board, hs, start[0], start[1], row, col, 0, visited, new StringBuilder(), new ArrayList<int[]>(), res);
helper(board, hm, start[0], start[1], row, col, 0, visited, new StringBuilder());
return shortest;
}
public static void helper(char[][] board, HashMap<Character, ArrayList<int[]>> hm, int r, int c, int row, int col, int count, int[][] visited, StringBuilder sb) {
// System.out.println(r + " " + c);
visited[r][c] = visited[r][c] + 1;
sb.append(r).append(c).append("->");
if (board[r][c] == '3') {
System.out.println(count);
if (shortest > count) {
path = sb.deleteCharAt(sb.length() - 1).deleteCharAt(sb.length() - 1).toString();
sb.append("->");
shortest = count;
}
//return;
//shortest = Math.min(shortest, count);
}
if (Character.isLowerCase(board[r][c])) { // if this is the key;
if (hm.containsKey(board[r][c])) {
for (int[] i : hm.get(board[r][c])) {
board[i[0]][i[1]] = '1';
}
}
}
if (r + 1 < row && board[r + 1][c] != '0' && visited[r + 1][c] < 2) {
helper(board, hm, r + 1, c, row, col, count + 1, visited, sb);
}
if (c + 1 < col && board[r][c + 1] != '0' && visited[r][c + 1] < 2) {
helper(board, hm, r, c + 1, row, col, count + 1, visited, sb);
}
if (r - 1 >= 0 && board[r - 1][c] != '0' && visited[r - 1][c] < 2) {
helper(board, hm, r - 1, c, row, col, count + 1, visited, sb);
}
if (c - 1 >= 0 && board[r][c - 1] != '0' && visited[r][c - 1] < 2) {
helper(board, hm, r, c - 1, row, col, count + 1, visited, sb);
}
visited[r][c] = visited[r][c] - 1;
sb.delete(sb.length() - 4, sb.length());
if (Character.isLowerCase(board[r][c])) { // if this is the key;
if (hm.containsKey(board[r][c])) {
for (int[] i : hm.get(board[r][c])) {
board[i[0]][i[1]] = '0';
}
}
}
return;
}
}
**あなたは答えとして何を得ましたか？デバッガであなたのアルゴリズムを踏んだことはありますか？ –
これを修正するには、デバッガを使用することが唯一の良い方法です。誰もが読んでバグを見つけられるようにするにはあまりにも多くのコードがあると私は思っています。 –