编程贪吃蛇蛇算法原理

来源：蜘蛛抓取(WebSpider) 时间：2018-04-16 08:38 标签： 推荐系统原理
这是一道大约15年这个时候我去某B开头的互联网公司面试时的一道基础算法题，其描述是有一只小老鼠，假设其在(x,y)点，它的初始方向为Y轴负半轴，它不能碰到x,y轴，也不能与自己走过的路径重合。并且其所走的所有坐标点必须&=(x,y),求它走过的路径和最终停在哪个点。
当时我并没有在限定时间解出这道题，如今在做BFS迷宫算法题时突然看到了两者存在某种一致性（当然本题更简单，并不需要用到BFS），勾起了陈年旧事，便一解以了。
其实本题最重要的思路有三点
1. 利用二维数组解坐标问题
这里需要注意的是，二维数组的行其实在数学一般坐标系中是Y轴，其列是X轴。然而直观上又会有行是X轴列是Y轴的印象。从前我经常边做边在心里置换，一会就把自己搞混乱了。其实坐标系只是相对的（相同的坐标值可以根据自己的偏好做出不同的坐标系，而其结果其实是相同的），即你可以直观地把行看成x，列看成y，只要你在作图的时候也按照这个概念，将x轴做成y，y轴做成x就可以了，需要注意的是，为了更加直观，可以取第四象限为作图起始。
2. 本题存在一个退出条件，即上下左右四个点都已经是visited，这样便需要在定义数组的时候多定义一行一列。其实用二维数组解坐标问题，本身就需要多定义一行一列（如果坐标点是（3,5），那么x有0,1,2,3四个数，需要四行存放），而本题中需要更多地定义一列（即如果坐标点是（3,5），数组应该是（3+2,5+2），否则在判断边界点时判断语句会因为数组溢出而报错。在初始化时需要将边界全部置为已经访问过的点（这些点本来就是不能触碰的）
3. 命名要有明确的含义，要直观，而不要绕弯。比如定义boolean visited[][]数组存放各个点的访问情况，如果已经访问了该节点，则置为true，如果还未访问，就是初始值false。虽然否定之否定是肯定，但如果命名为unvisited，再把结果倒置，实在是麻烦了自己也麻烦了程序。（T_T这就是我最初的做法，自己把自己搞凌乱了）
以上就是我做这道题的时的感悟了
public class loop {
public static int N = 5, M = 7;
public static void main(String args[]) {
int x = 3, y = 5;
boolean visited[][] = new boolean[5][7];
for (int i = 0; i & 7; i++) {
visited[0][i] =
visited[4][i] =
for (int i = 0; i & 5; i++) {
visited[i][0] =
visited[i][6] =
int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
System.out.println("Visit:(" + x + ", " + y + ")");
visited[x][y] =
while (x &= 1 && x &= N && y &= 1 && y &= M
&& (!visited[x + dir[0][0]][y + dir[0][1]] || !visited[x + dir[1][0]][y + dir[1][1]]
|| !visited[x + dir[2][0]][y + dir[2][1]] || !visited[x + dir[3][0]][y + dir[3][1]])) {
for (int i = 0; i & 4; i++) {
while (x &= 0 && x &= M && y &= 0 && y &= N && !visited[x + dir[i][0]][y + dir[i][1]]) {
x = x + dir[i][0];
y = y + dir[i][1];
visited[x][y] =
System.out.println(dir[i][0] + "," + dir[i][1]);
System.out.println(visited[x][y]);
System.out.println("Current Location:(" + x + ", " + y + ")");
System.out.println("The final point is:(" + x + ", " + y + ")");
阅读(...) 评论()1被浏览90分享邀请回答暂时还没有回答，开始写第一个回答博主最新文章
博主热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)博主最新文章
博主热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)4被浏览1,172分享邀请回答1添加评论分享收藏感谢收起

我要回帖

更多关于 推荐系统原理 的文章

 

随机推荐