赞
踩
现在市面上有很多扫地机器人,能够为我们分担家务,但是我们很难理解,有时候扫地机器人会重复清扫同一块地方。
public class FloormoppingRobot { private static int N = 12; //移动方向的列表,对应上下左右 private static List<Position> step = new ArrayList<>(4);; static { step.add(new Position(0,1)); step.add(new Position(0,-1)); step.add(new Position(1,0)); step.add(new Position(-1,0)); } private static int move(List<Position> historyPos){ //移动部署为N,则历史列表集合size为4时结束 if( historyPos.size() == N + 1){ return 1; } int cnt = 0; for( Position move : step ){ //取出列表里最后一个元素 int lastIndex = historyPos.size()-1; Position currentPosition = historyPos.get(lastIndex); //计算机器人下一步的位置 Position nextPosition = new Position(currentPosition.x+move.x, currentPosition.y + move.y); if( !historyPos.contains(nextPosition) ){ historyPos.add(nextPosition); cnt += move(historyPos); historyPos.remove(nextPosition); } } return cnt; } public static void main(String[] args) { List<Position> pos = new ArrayList<>(); pos.add(new Position(0,0)); List<Position> historyPos = new ArrayList<>(); int cnt = move(pos); System.out.println(cnt); } } class Position { int x; int y; public Position(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Position position = (Position) o; return x == position.x && y == position.y; } @Override public int hashCode() { return Objects.hash(x, y); } }
原书代码实现git库:https://github.com/allen1995/70-math-quizs-for-programmers
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。