jumps = {1: 38, 4: 14, 9: 31, 21: 42, 28: 84, 36: 44, 51: 67, 71: 91, 80: 100,
98: 78, 95: 75, 93: 73, 87: 24, 64: 60, 62: 19, 56: 53, 49: 11, 48: 26, 16: 6}
final_pos = 100
positions = {0} #initial position off the board
nsteps = 0
while final_pos not in positions:
nsteps += 1
old_positions = positions
positions = set()
for pos in old_positions:
for dice in range(1, 7):
new_pos = pos + dice
positions.add(jumps.get(new_pos, new_pos))
print 'Reached finish in %i steps' % nsteps
# the target square and the positions of the snakes and ladders:
top = 100
jump = { 1: 38, 4: 14, 9: 31, 16: 6, 21: 42, 28: 84, 36: 44,
48: 26, 49: 11, 51: 67, 56: 53, 62: 19, 64: 60, 71: 91,
80:100, 87: 24, 93: 73, 95: 75, 98: 78}
# start from square 0 (= outside the board) after 0 rolls
open = {0}
path = {0: ()}
while len(open) > 0:
i = open.pop()
p = path[i] + (i,)
for j in xrange(i+1, i+7):
if j > top: break
if j in jump: j = jump[j]
if j not in path or len(path[j]) > len(p):
open.add(j)
path[j] = p
for i in path:
print "Square", i, "can be reached in", len(path[i]), "rolls via", path[i]
jump字典）取自Bas Swinckels在他的答案中链接的博客文章。此代码将打印出到达棋盘上每个可到达方格的（其中之一）最短路径，以以下内容结束：Square 100 can be reached in 7 rolls via (0, 38, 41, 45, 67, 68, 74)
open.add(j) 之前不编写 if j in jump: j = jump[j]，那么就会出错。对吧？我刚看到了这个，担心他们编写的代码可能是错误的，因为他们没有将 jump[j] 放入队列中。请检查一下。 - ajaysinghnegishortest way awareness : When the algorithm gets to the target it will register the shortest way and during the calculation it will drop searches that are longer that the current found solution. That makes the process a lot faster in complex situations.
using System;
using System.Collections.Generic;
using System.Linq;
namespace SnakeAndLaddersSolution
{
public class SnakeAndLadder
{
private struct Jump
{
public int Start;
public int End;
}
private const int TOP = 100;
private const int STEP_SIZE = 6;
private int _minDiceCount = int.MaxValue;
private readonly List<Jump> _jumps = new List<Jump>();
public bool OptionalJump { get; set; }
public void AddJump(int start, int end)
{
_jumps.Add(new Jump { Start = start, End = end });
}
public int Solve()
{
var path = new Stack<int>();
path.Push(1); //start from square 1
return FindMinimumDice(path, 0);
}
private int FindMinimumDice(Stack<int> path, int diceCount)
{
if (diceCount >= _minDiceCount)
{
//too long. we've already found a shortest path.
//drop going deeper
return -1;
}
var currentSquare = path.Peek();
var diceCounts = new List<int>();
int newDiceCount;
var ignoreNormalJump = false;
for (var i = 0; i <= STEP_SIZE; i++)
{
var newSquare = currentSquare + i;
if (newSquare == TOP)
{
//got there
var totalDiceCount = diceCount + (i == 0 ? 0 : 1);
_minDiceCount = Math.Min(_minDiceCount, totalDiceCount); //register the shortest path
return totalDiceCount;
}
if (_jumps.All(j => j.Start != newSquare)) continue; //only process jumps
var jump = _jumps.First(j => j.Start == newSquare);
if (path.Contains(jump.End))
continue; //already been here
path.Push(jump.Start);
path.Push(jump.End);
newDiceCount = FindMinimumDice(path, diceCount + (i == 0 ? 0 : 1));
path.Pop();
path.Pop();
if (newDiceCount != -1)
diceCounts.Add(newDiceCount);
if (i == 0 && !OptionalJump) //the current squre is a jump that should be taken
{
ignoreNormalJump = true;
break;
}
}
if (!ignoreNormalJump)
{
var longestJump = 0;
for (var i = STEP_SIZE; i > 0; i--)
{
if (_jumps.All(j => j.Start != currentSquare + i))
{
longestJump = currentSquare + i;
break;
}
}
if (longestJump != 0)
{
path.Push(longestJump);
newDiceCount = FindMinimumDice(path, diceCount + 1);
path.Pop();
if (newDiceCount != -1)
diceCounts.Add(newDiceCount);
}
}
return !diceCounts.Any() ? -1 : diceCounts.Min();
}
}
class Program
{
static void Main(string[] args)
{
var sal = new SnakeAndLadder();
//set OptionalJump to true if the jump is optional
//sal.OptionalJump = true;
sal.AddJump(10,60);
sal.AddJump(51,100);
Console.WriteLine(sal.Solve());
Console.ReadLine();
}
}
}
这是用Python编程语言编写的贪吃蛇和梯子游戏代码。
简单的代码可以赢得贪吃蛇和梯子游戏。
**************** 贪吃蛇和梯子游戏代码 ***********************
import random
import curses
s = curses.initscr()
curses.curs_set(0)
sh, sw = s.getmaxyx()
w = curses.newwin(sh, sw, 0, 0)
w.keypad(1)
w.timeout(100)
snk_x = sw/4
snk_y = sh/2
snake = [
[snk_y, snk_x],
[snk_y, snk_x-1],
[snk_y, snk_x-2]
]
food = [sh/2, sw/2]
w.addch(food[0], food[1], curses.ACS_PI)
key = curses.KEY_RIGHT
while True:
next_key = w.getch()
key = key if next_key == -1 else next_key
if snake[0][0] in [0, sh] or snake[0][1] in [0, sw] or snake[0] in snake[1:]:
curses.endwin()
quit()
new_head = [snake[0][0], snake[0][1]]
if key == curses.KEY_DOWN:
new_head[0] += 1
if key == curses.KEY_UP:
new_head[0] -= 1
if key == curses.KEY_LEFT:
new_head[1] -= 1
if key == curses.KEY_RIGHT:
new_head[1] += 1
snake.insert(0, new_head)
if snake[0] == food:
food = None
while food is None:
nf = [
random.randint(1, sh-1),
random.randint(1, sw-1)
]
food =nf if nf not in snake else None
w.addch(food[0], food[1], curses.ACS_PI)
else:
tail = snake.pop()
w.addch(tail[0], tail[1], ' ')
w.addch(snake[0][0], snake[0][1], curses.ACS_CKBOARD)
广度优先搜索（BFS）或动态规划解决方案将使用O（N）时间和O（N）空间。
初始化：保持一个辅助数组来保存梯子和蛇。假设从第x个单元格到第y个单元格有一条梯子。因此，auxi [x] = y。如果从单元格x到y有蛇，x>y，则保持auxi [x] = -1。如果当前单元格没有梯子或蛇，则保持auxi [x] = x;
动态规划解决方案：
res[top]=0;
for(int i = top-1; i>=0; i--) {
res[i] = INF;
for(int j=1; j<=6; j++){
if(i-j<0)break;
if(auxi[i+j]>-1) // if i+jth cell is start of a snake, we'll always skip it
res[i]=min( res[i] , res[auxi[i+j]]+1 );
}
}
由于假设蛇在x单元格开始，结束在第yth单元格，我们将始终跳过蛇开始的单元格。
res 的元素。 - Ilmari Karonenres[i] = INF;。 - Fallenauxi[i-j] 可能会小于（通常是）i。 （我认为这可能是一个错误，应该是 auxi[i+j]，因为您正在从 top 向后循环到 0，但即使您修复了它，每当有蛇时仍然会引用未初始化的元素。） - Ilmari Karonenres是什么，表示从某个位置到达顶部需要的步数？你的算法是否考虑到解决方案可能同时上爬梯子和下滑蛇？不确定min()是否正确考虑了这一点，因为你似乎在查找可能会改变值的棋盘位置... - Bas Swinckelsres未初始化的部分，并且你没有在评论中回复这个批评。如果只有梯子，你的解决方案可能会起作用。但是，如果有一个从1到80的梯子，另一个从50到100的梯子和一个从81到49的蛇，它能找到解决方案吗？当i=80时，它还不知道49离终点只有一步之遥。你测试过自己的代码吗？ - Bas Swinckels这个程序模拟实际场景...请告诉我它是否符合期望...
import java.util.HashMap;
import java.util.Map;
public class SnakeLadder {
private Map<Integer,Integer> snakeLadderMapping=new HashMap<Integer,Integer>();
private int winPosition=100;
private int currentPosition=1;
public SnakeLadder(){
snakeLadderMapping.put(9, 19);
snakeLadderMapping.put(17, 5);
snakeLadderMapping.put(12, 40);
snakeLadderMapping.put(24, 60);
snakeLadderMapping.put(68, 89);
snakeLadderMapping.put(50, 12);
snakeLadderMapping.put(84, 98);
snakeLadderMapping.put(75, 24);
snakeLadderMapping.put(72, 16);
}
public int startGame(){
int count=0;
while(currentPosition!=winPosition){
count++;
getNextPosition(rollDice());
}
System.out.println("Game Won!!!!!!");
return count;
}
public int rollDice(){
return 1+ (int)(Math.random()*5);
}
public void getNextPosition(int diceValue){
int temp=currentPosition+diceValue;
if(snakeLadderMapping.containsKey(temp)){
currentPosition=snakeLadderMapping.get(temp);
}else{
if(temp<=winPosition){
currentPosition=temp;
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
SnakeLadder l=new SnakeLadder();
System.out.println("No of Steps to win:"+l.startGame());
}
}
在此处查看完整的代码解决方案 - https://algorithms.tutorialhorizon.com/snake-and-ladder-problem/
使用C#编写o(n)的解决方案。
构建一个帮助矩阵来遍历每一步，查看到达目标的最小路径并将其加1。
const int BoardSize = 100;
const int MaxStep = 6;
static void Main()
{
// - means a ledder ending at the pos
// + means a snake (taking you back n steps)
int[] arr = new int[] {
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 8, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -71, -1, -1 };
Console.WriteLine("Steps needed: " + solve(arr));
}
public static int solve(int[] inArr)
{
int[] arr = new int[BoardSize];
arr[0] = 1;
for (int i = 0; i < BoardSize; ++i)
{
// steps here is the minimum of all the positions in all the previos 6 cells +1
if (i < MaxStep)
arr[i] = 1;
else
{
int extraOption = int.MaxValue;
if (inArr[i] < -1 || inArr[i] > 0)
extraOption = arr[i + inArr[i]];
else if (inArr[i] > 0)
extraOption = arr[i + inArr[i]];
arr[i] = min(arr[i - 1], arr[i - 2], arr[i - 3], arr[i - 4], arr[i - 5], arr[i - 6], extraOption) + 1;
}
}
for (int i = 0; i < BoardSize; ++i)
{
Console.Write(arr[i] + "\t");
if ((i + 1) % 10 == 0)
Console.WriteLine("");
}
return arr[arr.Length-1];
}
public static int min(int a, int b, int c, int d, int e, int f, int g)
{
int ab = Math.Min(a,b);
int cd = Math.Min(c,d);
int ef = Math.Min(e,f);
return Math.Min(Math.Min(ab, cd), Math.Min(ef,g));
}