一个没有答案的有关问题
一个没有答案的问题
网上偶然看到的一个题，说是没有答案，想用程序试试能不能解开。求个解题思路，欢迎讨论，提供解题思路，给出代码更好
------解决思路----------------------
欢迎大家测试下，经测试只要是奇数点都无法完成。
------解决思路----------------------
------解决思路----------------------
我想了下，是个穷举的笨方法：
首先通过二维数组构建出地图，比如用1代表黑点，0代表白点[[0,1,0,0,0],[0,0,0,0,0]……]
然后就是关键的算法部分：（我是个懒人写下大体思路，不细致推敲）
①外层大循环，以每个0为起点走路线
②走路算法（关键中的关键）：
我们约定按照左、右、上、下的次序穷举走路，如果走不下去了就退到上一个步骤，直到找到全部走完的一条路线。
于是可以预见，需要个list存储步骤，已支持走路的“撤销功能”
基本的思路就是这样……
本来是上周五想回复的，后来被老大拉去开会了，周一回来发现连代码答案都有人发了。
郁闷……都没回复的兴致了
网上偶然看到的一个题，说是没有答案，想用程序试试能不能解开。求个解题思路，欢迎讨论，提供解题思路，给出代码更好
------解决思路----------------------
package com.vicky.study.test;
import java.util.ArrayList;
import java.util.List;
import org.junit.Before;
import org.junit.Test;
/**
* http://bbs.****.net/topics/391827822
*
* @author Administrator
*
*/
public class SomethingTest {
private Point[][] points = null;
private boolean[][] records = null;
private List<Point> road = new ArrayList<>(24);
Point black = null;
@Before
public void before() {
points = new Point[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
Point p = new Point(i, j);
points[i][j] = p;
// left
if (j - 1 >= 0) {
points[i][j - 1].setRight(p);
p.setLeft(points[i][j - 1]);
}
// up
if (i - 1 >= 0) {
points[i - 1][j].setDown(p);
p.setUp(points[i - 1][j]);
}
}
}
black = points[0][1];
}
@Test
public void test() {
for (int i = 0; i < points.length; i++) {
for (int j = 0; j < points[i].length; j++) {
// 重置
records = new boolean[5][5];
road.clear();
if (traverse(points[i][j])) {
System.out.println(road);
System.exit(1);
}
}
}
}
public boolean traverse(Point start) {
if (start == black) {// 黑名单，滚粗
return false;
}
if (records[start.getX()][start.getY()]) {// 已访问，滚粗
return false;
} else {
records[start.getX()][start.getY()] = true;// 设为已访问，如果下一个无法访问，还得还原回false
}
// 判断是否全部访问到了
boolean over = true;
for (int i = 0; i < records.length; i++) {
for (int j = 0; j < records[i].length; j++) {
if (!records[i][j] && (i != black.getX()
------解决思路----------------------
j != black.getY())) {
over = false;
break;
}
}
if (!over) {
break;
}
}
if (over) {// 全部都访问到了则返回
road.add(start);
return true;
}
// left
if (start.getLeft() != null && traverse(start.getLeft())) {
road.add(start);
return true;
}
// right
if (start.getRight() != null && traverse(start.getRight())) {
road.add(start);
return true;
}
// up
if (start.getUp() != null && traverse(start.getUp())) {
road.add(start);
return true;
}
// down
if (start.getDown() != null && traverse(start.getDown())) {
road.add(start);
return true;
}
// 路没走下去，那么将自己重新设为未遍历
records[start.getX()][start.getY()] = false;
return false;
}
}
class Point {
private final int x;
private final int y;
private Point left;
private Point right;
private Point up;
private Point down;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
public Point getLeft() {
return left;
}
public void setLeft(Point left) {
this.left = left;
}
public Point getRight() {
return right;
}
public void setRight(Point right) {
this.right = right;
}
public Point getUp() {
return up;
}
public void setUp(Point up) {
this.up = up;
}
public Point getDown() {
return down;
}
public void setDown(Point down) {
this.down = down;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + "]";
}
}
欢迎大家测试下，经测试只要是奇数点都无法完成。
------解决思路----------------------
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class MyGrid {
private static MyPoint[][] points;
public static void main(String[] args) {
setGrid(5, 5);
for (MyPoint[] myPoints : points) {
System.out.println(Arrays.toString(myPoints));
}
MyPoint start = points[0][1];
LinkedList<MyPoint> begin = new LinkedList<MyPoint>();
Track track = new Track(begin, start);
track.setStart(start);
track.move();
ArrayList<LinkedList<MyPoint>> answer = Track.getAll();
int max = 0;
for (LinkedList<MyPoint> linkedList : answer) {
if(linkedList.size() > max){
max = linkedList.size();
}
}
System.out.println(max);
}
/**
* 设置棋盘
* @param x
* @param y
*/
private static void setGrid(int x, int y) {
points = new MyPoint[x][y];
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
points[i][j] = new MyPoint(i, j);
}
}
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
if (i > 0) {
points[i][j].setUp(points[i - 1][j]);
}
if (i < x - 1) {
points[i][j].setDown(points[i + 1][j]);
}
if (j > 0) {
points[i][j].setLeft(points[i][j - 1]);
}
if (j < y - 1) {
points[i][j].setRight(points[i][j + 1]);
}
}
}
}
}
/**
* 表示棋盘上的点
* @author Administrator
*
*/
class MyPoint {
private int x;
private int y;
private MyPoint up;
private MyPoint down;
private MyPoint left;
private MyPoint right;
public MyPoint(int x, int y) {
super();
this.x = x;
this.y = y;
}
public void setUp(MyPoint up) {
this.up = up;
}
public void setDown(MyPoint down) {
this.down = down;
}
public void setLeft(MyPoint left) {
this.left = left;
}
public void setRight(MyPoint right) {
this.right = right;
}
public MyPoint getNext(int i) {
switch (i) {
case Direction.UP:
return up;
case Direction.DOWN:
return down;
case Direction.LEFT:
return left;
case Direction.RIGHT:
return right;
}
return null;
}
/**
* 根据轨迹计算下个点的方向
* @param track
* @return
*/
public Direction next(Track track) {
Direction d = new Direction();
List<MyPoint> list = track.getResult();
if (up != null && !list.contains(up)) {
d.setUp(Direction.UP);
}
if (down != null && !list.contains(down)) {
d.setDown(Direction.DOWN);
}
if (left != null && !list.contains(left)) {
d.setLeft(Direction.LEFT);
}
if (right != null && !list.contains(right)) {
d.setRight(Direction.RIGHT);
}
return d;
}
public boolean nextEquals(MyPoint p) {
if (up != null && up.equals(p)) {
return true;
}
if (down != null && down.equals(p)) {
return true;
}
if (left != null && left.equals(p)) {
return true;
}
if (right != null && right.equals(p)) {
return true;
}
return false;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MyPoint other = (MyPoint) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
@Override
public String toString() {
return "MyPoint [x=" + x + ", y=" + y + "]";
}
}
/**
* 轨迹
* @author Administrator
*
*/
class Track {
private static ArrayList<LinkedList<MyPoint>> all = new ArrayList<>();
private LinkedList<MyPoint> result = new LinkedList<MyPoint>();
private MyPoint start;
public Track(LinkedList<MyPoint> result, MyPoint mp) {
super();
this.result = result;
add(mp);
}
public void add(MyPoint mp) {
result.addLast(mp);
}
public static ArrayList<LinkedList<MyPoint>> getAll() {
return all;
}
public void setStart(MyPoint start) {
this.start = start;
}
public LinkedList<MyPoint> getResult() {
return result;
}
private void makeNewTrack(LinkedList<MyPoint> list, MyPoint mp) {
Track t = new Track(list, mp);
t.setStart(start);
t.move();
}
public void move() {
while (true) {
Direction d = result.getLast().next(this);
ArrayList<Integer> num = Direction.getDirectionNum(d);
int length = num.size();
if (length == 0) {
if (result.getLast().nextEquals(start)) {
all.add(result);
}
break;
}
if (length > 1) {
for (int i = 1; i < length; i++) {
MyPoint mp1 = result.getLast().getNext(num.get(i));
LinkedList<MyPoint> copy = (LinkedList<MyPoint>) result
.clone();
makeNewTrack(copy, mp1);
}
}
MyPoint mp = result.getLast().getNext(num.get(0));
add(mp);
}
}
}
class Direction {
public static final int UP = 1;
public static final int DOWN = 2;
public static final int LEFT = 3;
public static final int RIGHT = 4;
private int up;
private int down;
private int left;
private int right;
public Direction() {
}
public int getUp() {
return up;
}
public void setUp(int up) {
this.up = up;
}
public int getDown() {
return down;
}
public void setDown(int down) {
this.down = down;
}
public int getLeft() {
return left;
}
public void setLeft(int left) {
this.left = left;
}
public int getRight() {
return right;
}
public void setRight(int right) {
this.right = right;
}
public static boolean isDead(Direction d) {
if (d.getUp() != 1 && d.getDown() != 2 && d.getLeft() != 3
&& d.getRight() != 4) {
return true;
}
return false;
}
public static ArrayList<Integer> getDirectionNum(Direction d) {
ArrayList<Integer> num = new ArrayList<Integer>();
if (d.up == UP) {
num.add(UP);
}
if (d.down == DOWN) {
num.add(DOWN);
}
if (d.left == LEFT) {
num.add(LEFT);
}
if (d.right == RIGHT) {
num.add(RIGHT);
}
return num;
}
@Override
public String toString() {
return "Direction [up=" + up + ", down=" + down + ", left=" + left
+ ", right=" + right + "]";
}
}
------解决思路----------------------
我想了下，是个穷举的笨方法：
首先通过二维数组构建出地图，比如用1代表黑点，0代表白点[[0,1,0,0,0],[0,0,0,0,0]……]
然后就是关键的算法部分：（我是个懒人写下大体思路，不细致推敲）
①外层大循环，以每个0为起点走路线
②走路算法（关键中的关键）：
我们约定按照左、右、上、下的次序穷举走路，如果走不下去了就退到上一个步骤，直到找到全部走完的一条路线。
于是可以预见，需要个list存储步骤，已支持走路的“撤销功能”
基本的思路就是这样……
本来是上周五想回复的，后来被老大拉去开会了，周一回来发现连代码答案都有人发了。
郁闷……都没回复的兴致了