Robot area 机器人运动范围
有一个 m*n的矩阵,从【0,0】到【m-1,n-1】。机器人从【0,0】开始移动,每一次可以上下左右移动一格。不能出界,也不能进入行坐标与列坐标数字之和大于k的格子。计算机器人能到达多少个格子。
in:m = 2, n = 3, k = 1
out:6
in:m = 3, n = 1, k = 0
out:1
思路
使用BFS
,借助方向数组处理,移动的坐标扩展。扩展后计算坐标是否合法,是否sum<=k
因为记录的是到达的格子数,也就是说,统计出所有能被BFS
到的坐标点
public int movingCount(int m, int n, int k) {
if(k==0){
return 1;
}
int[] dum = new int[100];
for (int i = 0; i <10 ; i++) {
for (int j = 0; j < 10; j++) {
dum[i*10+j]=i+j;
}
}
HashSet<Integer> set = new HashSet<>();
Queue<int[]> queue = new LinkedList<int[]>();
int ans = 0;
set.add(0);
queue.offer(new int[]{0,0});
int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
while(!queue.isEmpty()){
int[] tmp = queue.peek();
ans++;
for(int d = 0;d<4;d++ ){
int x = tmp[0]+dir[d][0];
int y = tmp[1]+dir[d][1];
if(x<0||x>m-1){
continue;
}
if(y<0||y>n-1){
continue;
}
if(set.contains(x*n+y)){
continue;
}
if(dum[x]+dum[y]>k){
continue;
}
set.add(x*n+y);
queue.offer(new int[]{x,y});
}
queue.poll();
}
return ans;
}
Tag
BFS