l*******t 发帖数: 79 | 1 (3) 一个 2 *4 的数组不重复包含1-8这些整数,有3种操作
a) 上下两个row交换.
b) 所有元素向右shift一个位置
c) 中间4个元素,顺时针旋转90度
现在随便给一个这样的数组,最小复员到1234,5678的步骤。
在一亩三分地上看到的,求指点... | b******b 发帖数: 713 | 2 i will try the brute force way first:
1. create a hashmap, whose key is the sequence of the matrix, e.g. if the
array is: row0[1,2,3,4], row1[5,6,7,8], then key is [1,2,3,4,5,6,7,8], value
is the min step to revert it back to [1,2,3,4,5,6,7,8], put in [1,2,3,4,5,6
,7,8], 0 into the map.
2. write a recursive method,
int min(matrix)
{
if (map.contains(matrix.sequence)) return map.get(...);
opt1 = matrix.copy().swaprow();
int result = Integer.maxValue;;
if (!map.contains(op1))
{
map.put(opt1, min(opt1));
}
result = Math.min(result, 1 + map.get(opt1));
//do the same for rotate 90d, etc.
//forget you also need a visited set so if you see the sequence you
already tried, you can return immediately
}
【在 l*******t 的大作中提到】 : (3) 一个 2 *4 的数组不重复包含1-8这些整数,有3种操作 : a) 上下两个row交换. : b) 所有元素向右shift一个位置 : c) 中间4个元素,顺时针旋转90度 : 现在随便给一个这样的数组,最小复员到1234,5678的步骤。 : 在一亩三分地上看到的,求指点...
| s***c 发帖数: 639 | 3 从输入数组开始,recursive在3种操作上一个个的试,直到出现12345678为止。
记录出现过的,防止死环
【在 l*******t 的大作中提到】 : (3) 一个 2 *4 的数组不重复包含1-8这些整数,有3种操作 : a) 上下两个row交换. : b) 所有元素向右shift一个位置 : c) 中间4个元素,顺时针旋转90度 : 现在随便给一个这样的数组,最小复员到1234,5678的步骤。 : 在一亩三分地上看到的,求指点...
| x*******9 发帖数: 138 | | l*******t 发帖数: 79 | 5
value
,6
【在 b******b 的大作中提到】 : i will try the brute force way first: : 1. create a hashmap, whose key is the sequence of the matrix, e.g. if the : array is: row0[1,2,3,4], row1[5,6,7,8], then key is [1,2,3,4,5,6,7,8], value : is the min step to revert it back to [1,2,3,4,5,6,7,8], put in [1,2,3,4,5,6 : ,7,8], 0 into the map. : 2. write a recursive method, : int min(matrix) : { : if (map.contains(matrix.sequence)) return map.get(...); : opt1 = matrix.copy().swaprow();
| l*******t 发帖数: 79 | 6 thanks!
【在 s***c 的大作中提到】 : 从输入数组开始,recursive在3种操作上一个个的试,直到出现12345678为止。 : 记录出现过的,防止死环
|
|