首页 > 代码库 > CC150 8.2
CC150 8.2
8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot? FOLLOW UP Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.
class Pos { int x; int y; } interface Robot { Pos getPos(); void right(); void down(); } path(i, j) means how many path goes to Pos(i, j). Thus, path(i, j) = path(i - 1, j) + path(i , j - 1); path(0, 1) = path(1, 0) = 1; int path(int i, int j) { if ((i == 0 && j == 1) || (i == 1 && j == 0)) return 1; else return path(i - 1, j) + path(i, j - 1); } // If some squares are off limits. // Thus. path(x, y) = 0, if Pos(x, y) are the squares. int path(int i, int j, Set<Pos> offLimits) { if (offLimits.contains(Pos.at(i, j))) return 0; else if ((i == 0 && j == 1) || (i == 1 && j == 0)) return 1; else return path(i - 1, j) + path(i, j - 1); } // How to get all possible paths? // Define a path node, like list node. class PathNode { Pos pos; PathNode next; } PathNode run(PathNode node, Set<Pos> bombs, Pos target) { Validate.notNull(node); Validate.notNull(target); // Reach target if (target.equals(node.getPos())) return node; // This position is a bomb if (bombs != null && bombs.contains(node.getPos())) return null; Node right = run(new PathNode(node.right()); if (right != null) node.addNext(right); Node down = run(new PathNode(node.down())); if (down != null) node.addNext(down); return node; } // Return a tree, each path is the path.
CC150 8.2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。