【題目】
一款不會反復(fù)清掃同一地方的機(jī)器人,只能前后左右移動劲蜻。
第一次移動陆淀,有4種移動路徑。
第二次移動先嬉,有12種轧苫。
第三次移動,有36種疫蔓。
第四次移動含懊,有100種。
......
請問衅胀,第12次移動岔乔,有多少種移動路徑?
【解決思路1】
public static void main(String[] args) {
? ? ? ? System.out.println("掃地機(jī)器人移動種類:"+? RobotUtil.move(12,false));
}
/**
* 掃地機(jī)器人
*/
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);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //去掉重復(fù)的
? ? ? ? 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;
? ? }
}