|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.*; |
| 4 | + |
| 5 | +/** |
| 6 | + * Created by fishercoder1534 on 9/30/16. |
| 7 | + */ |
| 8 | +publicclassWallsAndGates { |
| 9 | +classBFS_solution_without_queue{ |
| 10 | + |
| 11 | +int[]dirs =newint[]{0,1,0,-1,0}; |
| 12 | +publicvoidwallsAndGates(int[][]rooms) { |
| 13 | +if(rooms ==null ||rooms.length ==0 ||rooms[0].length ==0)return; |
| 14 | +intm =rooms.length,n =rooms[0].length; |
| 15 | +for(inti =0;i <m;i++){ |
| 16 | +for(intj =0;j <n;j++){ |
| 17 | +if(rooms[i][j] ==0)bfs(rooms,i,j,m,n); |
| 18 | + } |
| 19 | + } |
| 20 | + } |
| 21 | + |
| 22 | +voidbfs(int[][]rooms,inti,intj,intm,intn){ |
| 23 | +for(intk =0;k <4;k++){ |
| 24 | +intx =dirs[k]+i; |
| 25 | +inty =dirs[k+1]+j; |
| 26 | +if(x >=0 &&y >=0 &&x <m &&y <n &&rooms[x][y] >rooms[i][j]+1) { |
| 27 | +rooms[x][y] =rooms[i][j]+1; |
| 28 | +bfs(rooms,x,y,m,n); |
| 29 | + } |
| 30 | + } |
| 31 | + } |
| 32 | + |
| 33 | + } |
| 34 | + |
| 35 | +classBFS_solution_with_a_queue{ |
| 36 | + |
| 37 | +//push all gates into the queue first, and then put all its neighbours into the queue with one distance to the gate, then continue to push the rest of the nodes into the queue, and put all their neighbours into the queue with the nodes' value plus one until the queue is empty |
| 38 | +int[]dirs =newint[]{0,1,0,-1,0}; |
| 39 | +publicvoidwallsAndGates(int[][]rooms) { |
| 40 | +if(rooms ==null ||rooms.length ==0 ||rooms[0].length ==0)return; |
| 41 | +intm =rooms.length,n =rooms[0].length; |
| 42 | +Queue<int[]>queue =newLinkedList(); |
| 43 | +for(inti =0;i <m;i++){ |
| 44 | +for(intj =0;j <n;j++){ |
| 45 | +if(rooms[i][j] ==0)queue.offer(newint[]{i,j}); |
| 46 | + } |
| 47 | + } |
| 48 | + |
| 49 | +while(!queue.isEmpty()){ |
| 50 | +int[]curr =queue.poll(); |
| 51 | +for(intk =0;k <4;k++){ |
| 52 | +intx =curr[0]+dirs[k]; |
| 53 | +inty =curr[1]+dirs[k+1]; |
| 54 | +if(x >=0 &&x <m &&y >=0 &&y <n &&rooms[x][y] ==Integer.MAX_VALUE) { |
| 55 | +rooms[x][y] =rooms[curr[0]][curr[1]]+1; |
| 56 | +queue.offer(newint[]{x,y}); |
| 57 | + } |
| 58 | + } |
| 59 | + } |
| 60 | + } |
| 61 | + |
| 62 | + } |
| 63 | +} |