java 斯坦福大学的一道java编程题（self-avoiding random walk）

Question

意思为首先要求用户输入grid网格的大小n*n,同时输入每个网格的像素点例如10pixels，从grid的中心开始行走，然后随机往四个方向行走，不能够碰触到本身，这样在n*n的网格中一直走到无法再走的地步。下面附上详细说明文件，希望懂java的朋友帮忙解决一下，有急用的。

Answer 1

和java关系不大,考察是的是算法呢喵~

Answer 2

事情的起因是源于下面这样的一则广告贴(目前幸运还没有被删除,可以链接成功): 
http://topic.csdn.net/u/20081028/15/525f32df-6c53-4b46-b847-f04c6fc1faf4.html 事情的发展是在这个贴: 我在移动平台专区被封权限是为什么?这个要找谁? 
http://topic.csdn.net/u/20081118/08/cf7d0af3-35cc-4fb7-9dc2-4567041b89e5.html?seed=1367941736 事情的最新进展是这样的: [抗议]对硬件/嵌入开发的某些版主武断,简单,粗暴的执法方式表示严重的抗议!  
http://topic.csdn.net/u/20081119/11/bda8bc5d-98d0-45ee-a1c1-86209d7f121d.html?seed=1457200066 当小贩被野蛮城管打死后之CSDN版 
http://topic.csdn.net/u/20081120/09/8af968cb-af00-4ddb-8604-dab1fb5421be.html?seed=613093649 我重申一下,我一直不是在为我发广告贴辩护,我是在为处理此事的过程中受到的不合理对待即wxf0204 武断,简单,粗暴加野蛮的方式执法的行为,就我看跟城官差不多,对残踏我作为CSDN网友尊严,无视我作为CSDN网友存在的言行进行回击,悍卫我作为CSDN网友所具有的最基本的权利,而且之前连一个申诉的地方都没有,也没有找到班主封ID,删除留言的规定!别人城管也不会第一次去执法看到有小贩就直接打死,也会先劝导,就第一次收了别人小贩的东西也会开个条说一下情况,开个清单,收了什么,什么时候来取,要受到何种处罚,你们这帮斑猪不通人性,看到小贩直接毙了,之前之后,不声不响,不闻不问,不通人性,比城管还城管...................
而且还不知反省,以暴抑暴,导致事件恶性循环!大家注意抗议的主题,不是对删除贴子,封ID有异议,对此贴前已经说的很清楚,现在的问题是抗议某些斑猪或者大部分斑猪在处理此事时粗暴的方式,野蛮的态度,狭隘的思想,如果在封ID之前给予警告,封ID之后对被封ID用户说明情况如确认被封的具体原因,封的时间以及当前所犯事件的严重程度等,事情何以至此,现在某些斑主为撑面子,继续执迷不悟,一点服务意识都没有,只会摆淫威! 再者跟城管没得比,别人城管之前还有警告,收了东西之后还要开个单子,通知什么时候去取回,有什么处罚,你们的粗野方式就是直接毙了,一了百了,跟原始人一样,难不成CSDN都是这样,真没人性化,我看别的论坛都是有流程,有说明,有警告,有通知!而且应该还有申诉的渠道,不能一手遮天,一毙完事,一点服务意识都没有,只会摆淫威! 
知会一下,举手之劳,别的论坛都这么做......你们不这么做就是不通人性.........你自己想下,你这样野蛮,我为何要惧怕你的淫威,你以为你是谁,做错事直接闷棍打死,真正怎么死的都不知,...........不给没有前科的人以任何机会,手段之残忍,心恨之至极...........令人发指........让人不服,还不让辩解.....................,一点服务意识都没有,只会摆淫威 
一点服务意识都没有,只会摆淫威

Answer 3

先翻译一下，占位，有空再贴代码：练习在这个练习中，你将要开发一个绘制“避开自身的随机行走”的程序，“避开自身的随机行走”是一条从一点到另一点的路径，它永远不和自身相交。最容易的实现方法是在网格上构造这条路径，这样步的长度是固定的，并且仅在离散个数的方向内。避开自身的随机行走，其中每一个网格点上的方向是随机选择的，它产生于多种物理模型，包括蛋白质折叠、布朗运动和聚合物链中。（图）
一个避开自身的随机行走的七次迭代。红色点标记为行走的起始点。在最后一次迭代时，没有未被占用的网格位置来移动了，所以行走结束。你的程序应该按如下方式工作：首先，用户被请求输入网格尺寸和每个单元格在图形屏幕上占用的像素数，然后，一条避开自身的随机行走路线从网格的中央开始构造。你将需要使用一个二维数组来记录网格点是否被占用。程序应该在每次迭代时检查当前网格点的直接上下左右方向上的网格点，其中的一个未被占用的网格点会被随机选择，它将成为下一个网格位置。如果当前网格点周围的网格点都被占用，则不可能再前进，路径结束。然后用户应该被询问是否重来一次，如果是，则清除图形屏幕并绘制另一条路径（使用相同的网格尺寸），否则，程序终止。
网格尺寸40x40，每个单元格10像素
（图）网格尺寸100x100，每个单元格5像素
（图）
像通常一样，先写下算法并用演示器检查，再试图去写程序。提示：你会发现java.util.Random类有用。

Answer 4

题目本身很简单，会基本的JAVA GUI就能写出来。比如下面就是我写的：不过，当你实际运行这个程序时，你会发现路径终止得非常快。其实关键在于选择下一个位置的算法是否对历史进行回顾和对未来进行展望，如果算法能考虑这两点，路径会走得比较长。我的算法很简单，路径一般在10步左右就终止了。我想斯坦福大学应该是借助这题来激发学生设计更好的算法吧，仅就题目本身来说是很简单的。package test;import javax.swing.JFrame;
import javax.swing.JOptionPane;
import java.awt.Graphics;
import java.util.Random;public class SelfAvoidingRandomWalk extends JFrame implements Runnable {

private int size;
private int squarePixels;
private boolean[][] pointsOccupied;
private int[] currentPosition = new int[2], nextPosition = new int[2];

private Thread thread;
private Random random;

public SelfAvoidingRandomWalk(int gridSize, int gridSquarePixels) {
super("Self Avoiding Random Walk");
size = gridSize;
squarePixels = gridSquarePixels;
setSize(size*squarePixels, size*squarePixels);
setVisible(true);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
pointsOccupied = new boolean[size][];
for (int i = 0; i < size; i++)
pointsOccupied[i] = new boolean[size];
thread = new Thread(this);
random = new Random();
reset();
}

public void reset() {
currentPosition[0] = nextPosition[0] = currentPosition[1] = nextPosition[1] = size/2;
for (int i = 0; i < size; i++)
java.util.Arrays.fill(pointsOccupied[i], false);
pointsOccupied[size/2][size/2] = true;
}

public void draw() {
thread.start();
}

public void run() {
while(true) {
if (!randomChooseNext()) break;
repaint();
try {
Thread.sleep(1*100);
} catch(Exception e) { }
}
if (JOptionPane.showConfirmDialog(this, "Path ends. Still want to see another one?") == JOptionPane.YES_OPTION) {
getGraphics().clearRect(0, 0, size*squarePixels, size*squarePixels);
reset();
run();
}
System.exit(0);
}

public void paint(Graphics g) {
g.drawLine(currentPosition[0]*squarePixels, currentPosition[1]*squarePixels, nextPosition[0]*squarePixels, nextPosition[1]*squarePixels);
currentPosition[0] = nextPosition[0];
currentPosition[1] = nextPosition[1];
}

private boolean randomChooseNext() {
int dirsAvailable = 4;
int newX, newY;
int dir;
while (dirsAvailable>0) {
newX = currentPosition[0];
newY = currentPosition[1];
dir = random.nextInt(4);
switch(dir) {
case 0: // left
newX--;break;
case 1: // top
newY--; break;
case 2: // right
newX++; break;
case 3: // bottom
newY++; break;
}
if (newX<0 || newY<0 || newX>size-1 || newY>size-1 || pointsOccupied[newX][newY])
dirsAvailable--;
else {
nextPosition[0] = newX;
nextPosition[1] = newY;
pointsOccupied[newX][newY] = true;
return true;
}
}
return false;
}

public static void main(String[] args) {
String input;
int size, squarePixels;
while (true) {
input = JOptionPane.showInputDialog("Please tell me the size of the grid you want to create (between 10 to 100):");
try {
size = Integer.parseInt(input);
if (size < 10 || size > 100) throw new Exception();
break;
} catch (Exception e) {
JOptionPane.showMessageDialog(null, "Sorry, input unacceptable. Please try again.");
}
}
while (true) {
input = JOptionPane.showInputDialog("Now please tell me the number of pixels of each grid square (between 5 to 10):");
try {
squarePixels = Integer.parseInt(input);
if (squarePixels < 5 || squarePixels > 10) throw new Exception();
break;
} catch (Exception e) {
JOptionPane.showMessageDialog(null, "Sorry, input unacceptable. Please try again.");
}
}
SelfAvoidingRandomWalk frame = new SelfAvoidingRandomWalk(size, squarePixels);
frame.draw();
}}