通过M×N个网格之旅号码? [英] Number of tours through m x n grid?
问题描述
让T(X,Y)是旅游的人数超过一X×Y网格这样:
Let T(x,y) be the number of tours over a X × Y grid such that:
- 巡演开始在左上角方形
- 旅游由动作是上,下,左,右一平方,
- 游览参观每平方米只出现一次,而
- 游左下方广场结束。
可以很容易地看到,例如,T(2,2)= 1,T(3,3)= 2,T(4,3)= 0,和T(3,4)= 4。 编写一个程序来计算T(10,4)。
It’s easy to see, for example, that T(2,2) = 1, T(3,3) = 2, T(4,3) = 0, and T(3,4) = 4. Write a program to calculate T(10,4).
- 我一直在这几个小时......我需要一个程序,它的网格的尺寸输入并返回可能的旅行团多少?如何,我应该去解决呢? 任何想法
推荐答案
既然你是新的回溯,这可能会给你一个想法如何,你可以解决这个问题:
Since you're new to backtracking, this might give you an idea how you could solve this:
您需要一些数据结构来重新present细胞的状态,对电网(访问/未被访问)。
You need some data structure to represent the state of the cells on the grid (visited/not visited).
您的算法:
step(posx, posy, steps_left)
if it is not a valid position, or already visited
return
if it's the last step and you are at the target cell
you've found a solution, increment counter
return
mark cell as visited
for each possible direction:
step(posx_next, posy_next, steps_left-1)
mark cell as not visited
和运行
step(0, 0, sizex*sizey)
回溯的基本构建块是:评估当前状态,标记,递归步骤和不标记
The basic building blocks of backtracking are: evaluation of the current state, marking, the recursive step and the unmarking.
这将正常工作的小板。真正的乐趣开始,你必须切枝对不属于可解树大板。(如:有没有到过的细胞的不可达区域)
This will work fine for small boards. The real fun starts with larger boards where you have to cut branches on the tree which aren't solvable (eg: there's an unreachable area of not visited cells).
这篇关于通过M×N个网格之旅号码?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!