拼多多线下笔试/机器人寻址题目，思路分享，求助

题目：

3. 房间里面有一个机器人位于位置(0, 0)。房间的形状和面积都是未知的。你可以通过一个遥控器来控制机器人往前后左右四个方向中的任何一个移动一个格子。移动的函数是 boolean move(int direction), direction: 0, 1, 2, 3。如果机器人发现移动方向上被墙壁挡住，这个方***返回 false，否则这个函数就会返回 true，机器人就会移动到相应的位置。请实现一个函数，来找到房间的面积。注：房间的形状是不规则的，但是是由许多大小为 1x1 的格子组成的，比如下图表示的房子里面，每一个 X 表示一个格子，房间的总面积是 10

X XXX X XXXXX

思路分享/代码：

代码有点乱，肯定是跑不通的，思路是

1.因为不知道矩阵多大，用map+map存坐标和是否访问过

2.用回溯法来做这道题

不知道想法对不对，如果有兴趣的可以交流一下，多谢

import java.util.HashMap; import java.util.Map;  /**  * @Author:zhangzy  * @Date:2017/11/18  */  public class test2 { public static int solution() {
        Map<Integer, Map<Integer, Boolean>> map = new HashMap<>();  return helper(0,0,map);   } public static int helper(int x, int y, Map<Integer, Map<Integer, Boolean>> map){ int up = 0, down = 0,left = 0, right = 0;  if(map.containsKey(x)){ if(map.get(x).containsKey(y)) { return 0;  } else {
                map.get(x).put(y , true);  }
        } else {
            Map<Integer ,Boolean> temp = new HashMap<>();  temp.put(y , true);  map.put(x , temp);  } if (move(0)) {
             up = helper(x - 1 , y ,map);  } if (move(1)) {
             down = helper(x + 1 , y ,map);  } if (move(2)) {
            left = helper(x , y - 1 ,map);  } if (move(3)) {
            right = helper(x , y + 1 ,map);  } return up + down + left + right + 1;  } 
//这里只是声明一下 public static boolean move(int direction){ return true;  }
}

#Java工程师#

全部评论

推荐最新楼层

Ga_li_dun_farming_guy

阿里巴巴_淘菜菜_研发工程师

广搜加深搜，每一步判断可以网哪个方向走，然后广搜，递归深搜

点赞回复分享

发布于 2017-11-18 19:01

孟靖宇

中国矿业大学 Java

用到了回溯。具体步骤是这样的： 1、计算当前位置可以前进的方向。可以前进的判断方式是：该方向的下一个位置没有到达过且该方向的下一个位置没有障碍。使用Set存储机器人到达过的位置。 2、遍历可以前进的方向，递归进行试探，边界条件是：当前位置没有可以移动的方向。此时跳出该层，回溯到上一个位置，向上一个位置的另一个可移动方向进行试探。 3、递归结束后，计算Set中元素的个数，即为房间的面积。代码亲测可用。 import java.util.*; public class Main{ static int x=0,y=0;//初始机器人位置 public static boolean move (int dir){//为了测试，自己写了一个move方法，比较片面 int[][] array= {//地图矩阵 {0,0,0,0,0,0,0,1,1,1,1,1}, {0,0,0,0,1,1,1,1,1,1,1,1}, {0,0,0,0,0,0,1,1,1,1,1,1}, {0,0,0,0,0,0,0,0,0,1,1,1}, {0,0,0,0,0,0,0,1,1,1,1,1}, {0,0,0,0,1,1,1,1,1,1,1,1} }; int x_m=array.length; int y_m=array[0].length; switch(dir) { case 0: if(y+1>=y_m || array[x][y+1]!=0) { return false; } y++; break; case 1: if(x+1>=x_m || array[x+1][y]!=0) { return false; } x++; break; case 2: if(y-1<0 || array[x][y-1]!=0) { return false; } y--; break; case 3: if(x-1<0 || array[x-1][y]!=0) { return false; } x--; break; default: break; } return true; } //计算面积的函数 public static int problem3 (int x,int y,Set<String> set){ set.add(x+","+y); //如果方向0的位置未到达过，且该位置没有障碍物，则移动到该位置。 if(!set.contains(x+","+(y+1)) && move(0)) { problem3 (x,y+1,set);//迭代计算下一个位置的情况 move(2);//回溯 } if(!set.contains((x+1)+","+y) && move(1)) { problem3 (x+1,y,set); move(3); } if(!set.contains(x+","+(y-1)) && move(2)) { problem3 (x,y-1,set); move(0); } if(!set.contains((x-1)+","+y) && move(3)) { problem3 (x-1,y,set); move(1); } return set.size(); } public static void main(String[] String){ Set<String> set=new HashSet<String>(); System.out.println(problem3(0,0,set)); } }

点赞回复分享

发布于 2018-03-03 23:55

温温

北京大学算法工程师

思路挺对的啊，用set存会不会更好

点赞回复分享

发布于 2017-12-05 12:03

sandyone

上海交通大学算法工程师

你能不能分享一下代码

点赞回复分享

发布于 2017-12-05 11:11