笔试题求解！！

马不是走"日"吗？
那C4到D3不是2不就OK了？
比如：C4->B2->D3
求解释.

这里的每步就是一个相同的权值（1步）
所以想求最短路径就可以直接用BFS了

不保证有误，囧。import java.awt.Point;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Test {

public static void main(String[] args) {
Test t = new Test();
if (!t.init()) {
t.bsf();
t.dsf(t.end);
t.print(t.path);
}
}

int length = 8;
int[][] map = new int[10][10];
Scanner in = new Scanner(System.in);
boolean isFound = false;
int dirx[] = { 1, 2, 2, 1,-1,-2,-2,-1};
int diry[] = {-2,-1, 1, 2, 2, 1,-1,-2};
Point start, end;
Queue<Point> queue = new LinkedList<Point>();
LinkedList<Point> path = new LinkedList<Point>();

// 初始化
boolean init() {
isFound = false;
for (int i = 0; i < map.length; i++) {
Arrays.fill(map[i], 0);
}
// 棋盘的四周
for (int i = 0; i < length + 1; i++) {
map[i][0] = -1;
map[i][length+1] = -1;
map[0][i] = -1;
map[length+1][i] = -1;
}
// 起点,终点
start = spit(in.next());
end = spit(in.next());
if (start.equals(end)) {
// 终点等于起点, 是否需要输出???
print(end);
return true;
}
queue.add(start);
return false;
}

// 解析坐标
Point spit(String str) {
Point tmp = new Point();
tmp.x = str.charAt(0) - 'A' + 1;
tmp.y = str.charAt(1) - '0';
return tmp;
}

// 广度优先搜索
void bsf() {
Point tmp, cnt = start;
map[cnt.x][cnt.y] = 1;
while(!queue.isEmpty())
{
cnt = queue.poll();
for (int i = 0; i < dirx.length; i++) {
tmp = new Point();
tmp.x = cnt.x + dirx[i];
tmp.y = cnt.y + diry[i];
if (map[tmp.x][tmp.y] == 0) {
queue.add(tmp);
map[tmp.x][tmp.y] = map[cnt.x][cnt.y] + 1;
if (tmp.equals(end)) {
return;
}
}
}
}
}

// 回溯读取路径
void dsf(Point scnt) {
if (isFound || scnt.equals(start)) {
isFound = true;
return;
} else {
path.addFirst(scnt);
for (int i = 0; i < dirx.length; i++) {
if (map[scnt.x + dirx[i]][scnt.y + diry[i]] == map[scnt.x][scnt.y] - 1) {
Point tmp = new Point();
tmp.x = scnt.x + dirx[i];
tmp.y = scnt.y + diry[i];
dsf(tmp);
}
}
}
}

// 输出
void print(LinkedList<Point> path) {
if (path.size() < 1) return;
int i = 0;
for (; i < path.size() - 1; i++) {
print(path.get(i));
System.out.print(" ");
}
print(path.get(i));
}

// 输出
void print(Point point) {
System.out.print(((char)(point.x - 1 + 'A')) + "" + point.y);
}
}

package net.csdn;import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;class Test { private static String[][] arr = null; public static void main(String[] args) throws Exception { String start = "C4";
String end = "C5";

arr = create();
List<String> l = search(next(), start, end);
l.remove(0);
System.out.println("=========PATH==========");
System.out.println(Arrays.toString(l.toArray(new String[0])));
}

private static List<String> search(Map<String, List<String>> map, String s, String e) {

Map<String, String> pre = new HashMap<String, String>();
LinkedList<String> q = new LinkedList<String>();
LinkedList<String> result = null;

q.addLast(s);
while(!q.isEmpty()) {

String c = q.removeFirst();
List<String> ps = map.get(c);
if (ps != null) {

for (String o : ps) {
if (pre.get(o) == null) {
pre.put(o, c);
q.addLast(o);
}
}
}
}
pre.put(s, null);

if (pre.get(e) != null) {
result = new LinkedList<String>();
for (String str = e; str != null ; str = pre.get(str)) {
result.addFirst(str);
}
}
return result;
}

private static Map<String, List<String>> next() {

Map<String, List<String>> map = new TreeMap<String, List<String>>();
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
List<String> list = new ArrayList<String>();
if (leftup(arr[i][j]) != null) {
list.add(leftup(arr[i][j]));
}
if (leftdown(arr[i][j]) != null) {
list.add(leftdown(arr[i][j]));
}
if (rightup(arr[i][j]) != null) {
list.add(rightup(arr[i][j]));
}
if (rightdown(arr[i][j]) != null) {
list.add(rightdown(arr[i][j]));
}
if (upleft(arr[i][j]) != null) {
list.add(upleft(arr[i][j]));
}
if (upright(arr[i][j]) != null) {
list.add(upright(arr[i][j]));
}
if (downleft(arr[i][j]) != null) {
list.add(downleft(arr[i][j]));
}
if (downright(arr[i][j]) != null) {
list.add(downright(arr[i][j]));
}
map.put(arr[i][j], list);
}
}
return map;
} private static String[][] create() { String[][] arr = new String[8][8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
arr[i][j] = String.valueOf((char) (j + 'A')) + (8 - i);
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
return arr;
}

private static String leftup(String p) {
p = left(p, 2);
p = up(p, 1);
return p;
}

private static String leftdown(String p) {
p = left(p, 2);
p = down(p, 1);
return p;
}

private static String rightup(String p) {
p = right(p, 2);
p = up(p, 1);
return p;
}

private static String rightdown(String p) {
p = right(p, 2);
p = down(p, 1);
return p;
}

private static String upleft(String p) {
p = up(p, 2);
p = left(p, 1);
return p;
}

private static String upright(String p) {
p = up(p, 2);
p = right(p, 1);
return p;
}

private static String downleft(String p) {
p = down(p, 2);
p = left(p, 1);
return p;
}

private static String downright(String p) {
p = down(p, 2);
p = right(p, 1);
return p;
}

private static String left(String p, int a) {

if (p == null) {
return null;
}
String pos = find(p);
if (pos == null) {
return null;
}
int x = Integer.parseInt(pos.split(",")[0]);
int y = Integer.parseInt(pos.split(",")[1]); if (x - a <= 0) {
return null;
}
return arr[x - a][y];
} private static String right(String p, int a) {

if (p == null) {
return null;
}
String pos = find(p);
if (pos == null) {
return null;
}
int x = Integer.parseInt(pos.split(",")[0]);
int y = Integer.parseInt(pos.split(",")[1]); if (x + a >= 8) {
return null;
}
return arr[x + a][y];
} private static String up(String p, int a) {

if (p == null) {
return null;
}
String pos = find(p);
if (pos == null) {
return null;
}
int x = Integer.parseInt(pos.split(",")[0]);
int y = Integer.parseInt(pos.split(",")[1]); if (y - a <= 0) {
return null;
}
return arr[x][y - a];
} private static String down(String p, int a) {

if (p == null) {
return null;
}
String pos = find(p);
if (pos == null) {
return null;
}
int x = Integer.parseInt(pos.split(",")[0]);
int y = Integer.parseInt(pos.split(",")[1]); if (y + a >= 8) {
return null;
}
return arr[x][y + a];
} private static String find(String p) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if (p.equals(arr[i][j])) {
return i + "," + j;
}
}
}
return null;
}
}

异常是数组下表越界了，判断下就好。import java.awt.Point;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Test {

public static void main(String[] args) {
Test t = new Test();
if (!t.init()) {
t.bsf();
t.dsf(t.end);
t.print(t.path);
}
}

int length = 8;
int[][] map = new int[10][10];
Scanner in = new Scanner(System.in);
boolean isFound = false;
int dirx[] = { 1, 2, 2, 1,-1,-2,-2,-1};
int diry[] = {-2,-1, 1, 2, 2, 1,-1,-2};
Point start, end;
Queue<Point> queue = new LinkedList<Point>();
LinkedList<Point> path = new LinkedList<Point>();

// 初始化
boolean init() {
isFound = false;
for (int i = 0; i < map.length; i++) {
Arrays.fill(map[i], 0);
}
// 棋盘的四周
for (int i = 0; i < length + 1; i++) {
map[i][0] = -1;
map[i][length+1] = -1;
map[0][i] = -1;
map[length+1][i] = -1;
}
// 起点,终点
start = spit(in.next());
end = spit(in.next());
if (start.equals(end)) {
// 终点等于起点, 是否需要输出???
print(end);
return true;
}
queue.add(start);
return false;
}

// 解析坐标
Point spit(String str) {
Point tmp = new Point();
tmp.x = str.charAt(0) - 'A' + 1;
tmp.y = str.charAt(1) - '0';
return tmp;
}

// 广度优先搜索
void bsf() {
Point tmp, cnt = start;
map[cnt.x][cnt.y] = 1;
while(!queue.isEmpty())
{
cnt = queue.poll();
for (int i = 0; i < dirx.length; i++) {
tmp = new Point();
tmp.x = cnt.x + dirx[i];
tmp.y = cnt.y + diry[i];
if (!check(tmp.x, tmp.y)) {
continue;
}
if (map[tmp.x][tmp.y] == 0) {
queue.add(tmp);
map[tmp.x][tmp.y] = map[cnt.x][cnt.y] + 1;
if (tmp.equals(end)) {
return;
}
}
}
}
}

// 回溯读取路径
void dsf(Point scnt) {
if (isFound || scnt.equals(start)) {
isFound = true;
return;
} else {
path.addFirst(scnt);
for (int i = 0; i < dirx.length; i++) {
if (!check(scnt.x + dirx[i], scnt.y + diry[i]) || !check(scnt.x, scnt.y)) {
continue;
}
if (map[scnt.x + dirx[i]][scnt.y + diry[i]] == map[scnt.x][scnt.y] - 1) {
Point tmp = new Point();
tmp.x = scnt.x + dirx[i];
tmp.y = scnt.y + diry[i];
dsf(tmp);
}
}
}
}

// 检查坐标
boolean check(int x, int y) {
if (x < 0 || x > 9 || y < 0 || y > 9)
return false;
return true;
}

// 输出
void print(LinkedList<Point> path) {
if (path.size() < 1) return;
int i = 0;
for (; i < path.size() - 1; i++) {
print(path.get(i));
System.out.print(" ");
}
print(path.get(i));
}

// 输出
void print(Point point) {
System.out.print(((char)(point.x - 1 + 'A')) + "" + point.y);
}
}

非常感谢您的代码，对我帮助很大。
代码中有几个错误：
1、 down方法和up方法的逻辑弄反了
2、在down方法和left方法中，y-a和x-a都可以等于0的
如果加上注释就更好了。已经是很好的代码，给我很大帮助了。谢谢。

调试易

笔试题求解！！

解决方案 »