【题目】
一款不会反复清扫同一地方的机器人，只能前后左右移动。
第一次移动，有4种移动路径。
第二次移动，有12种。
第三次移动，有36种。
第四次移动，有100种。
......
请问，第12次移动，有多少种移动路径？
【解决思路1】
public static void main(String[] args) {
System.out.println("扫地机器人移动种类："+ RobotUtil.move(12,false));
}
/**
* 扫地机器人
*/
public class RobotUtil {
public static long move(int max,boolean isPrint){
List<Point> l = new ArrayList<>();
l.add(new Point(-1,0));
l.add(new Point(1,0));
l.add(new Point(0,1));
l.add(new Point(0,-1));
List<List<Point>> list = new ArrayList<>();
List<List<Point>> list2 = new ArrayList<>();
//初始化【0，0】
List<Point> list1 = new ArrayList<>();
list1.add(new Point(0,0));
list.add(list1);
//添加所有可能
for(int i=1;i<=max;i++) {
//清空另存
list2.clear();
list2.addAll(list);
list.clear();
for(int m=0;m<list2.size();m++) {
for (int j = 0; j < l.size(); j++) {
List<Point> list3 = new ArrayList<>();
list3.addAll(list2.get(m));
Point a1 = list3.get(list3.size()-1);
Point a2 = l.get(j);
list3.add(new Point(a1.getX()+a2.getX(),a1.getY()+a2.getY()));
list.add(list3);
}
}
}
//去掉重复的
list2.clear();
list2.addAll(list);
list.clear();
for(int i=0;i<list2.size();i++){
List<Point> list3 = list2.get(i);
List<Point> list4 = new ArrayList<>();
for(int j=0;j<list3.size();j++){
int x = list3.get(j).getX();
int y = list3.get(j).getY();
int isExist = 0;
for(int m=0;m<list3.size();m++){
int x1 = list3.get(m).getX();
int y1 = list3.get(m).getY();
if(x==x1&&y==y1){
isExist++;
}
}
if(isExist==1){
list4.add(list3.get(j));
}
}
if(list4.size()==(max+1)){
if(isPrint) {
for (int t = 0; t < list3.size(); t++) {
System.out.print("[" + list3.get(t).getX() + "," + list3.get(t).getY() + "] ");
}
System.out.print("\r\n");
}
list.add(list3);
}
}
return list.size();
}
}
public class Point {
Point(int x, int y) {
this.x = x;
this.y = y;
}
private int x;
private int y;
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public void setY(int y) {
this.y = y;
}
public int getY() {
return y;
}
}
