墙与门

https://leetcode-cn.com/problems/walls-and-gates/

  1. typedef struct{
  2.     int x;
  3.     int y;
  4. } Position;
  6. Position p[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  8. void wallsAndGates(int** rooms, int roomsSize, int* roomsColSize){
  9.     int total = roomsSize * (*roomsColSize);
  10.     Position * queue = malloc(sizeof(Position) * total);
  11.     int front = 0, rear = 0, num = 0;
  12.     for(int i = 0; i < roomsSize; i++){
  13.         for(int j = 0; j < *roomsColSize; j++){
  14.             if(rooms[i][j] == 0){
  15.                 queue[rear].x = i;
  16.                 queue[rear].y = j;
  17.                 rear = (rear + 1) % total;
  18.                 num++;
  19.             }
  20.         }
  21.     }
  22.     while(num != 0){
  23.         Position cur = queue[front];
  24.         num--;
  25.         front = (front + 1) % total;
  26.         for(int i = 0; i < 4; i++){
  27.             int x = cur.x + p[i].x;
  28.             int y = cur.y + p[i].y;
  29.             if(x >= 0 && x < roomsSize && y >= 0 && y < *roomsColSize && rooms[x][y] == 2147483647){
  30.                 rooms[x][y] = rooms[cur.x][cur.y] + 1;
  31.                 queue[rear].x = x;
  32.                 queue[rear].y = y;
  33.                 rear = (rear + 1) % total;
  34.                 num++;
  35.             }
  36.         }
  37.     }
  38. }
  1. class Solution {
  3.     Queue<int[]> q = new LinkedList<int[]>();
  4.     int[][] directions = {{1, 0},{-1, 0},{0, 1},{0, -1}};
  5.     int x;
  6.     int y;
  8.     public void wallsAndGates(int[][] rooms) {
  9.         if(rooms == null)
  10.             return;
  11.         x = rooms.length;
  12.         y = rooms[0].length;
  13.         for(int i = 0; i < x; i++){
  14.             for(int j = 0; j < y; j++){
  15.                 if(rooms[i][j] == 0){
  16.                     q.add(new int[]{i, j});
  17.                 }
  18.             }
  19.         }
  20.         bfs(rooms);
  21.     }
  23.     public void bfs(int[][] rooms, int){
  25.         int nextX;
  26.         int nextY;
  28.         while(!q.isEmpty()){
  29.             int[] cur = q.poll();
  30.             for(int[] direction: directions){
  31.                 nextX = cur[0] + direction[0];
  32.                 nextY = cur[1] + direction[1];
  33.                 if(nextX >= x || nextX < 0 || nextY < 0 || nextY >= y || rooms[nextX][nextY] != 2147483647)
  34.                     continue;
  35.                 rooms[nextX][nextY] =  rooms[cur[0]][cur[1]] + 1;
  36.                 q.add(new int[]{nextX, nextY});
  37.             }
  38.         }
  40.     }
  41. }

岛屿数量

https://leetcode-cn.com/problems/number-of-islands/

  1. typedef struct{
  2.     int x;
  3.     int y;
  4. } Position;
  6. Position p[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  9. int numIslands(char** grid, int gridSize, int* gridColSize){
  10.     int total = gridSize * (*gridColSize);
  11.     Position * queue = (Position *)malloc(sizeof(Position) * total);
  12.     int rear = 0, front = 0, num = 0, count = 0;
  13.     for(int i = 0; i < gridSize; i++){
  14.         for(int j = 0 ; j < *gridColSize; j++){
  15.             if(grid[i][j] == '1'){
  16.                 grid[i][j] = '0';
  17.                 count++;
  18.                 queue[rear].x = i;
  19.                 queue[rear].y = j;
  20.                 num++;
  21.                 rear = (rear + 1) % total;
  22.             }
  23.             //遍历每一座岛
  24.             while(num != 0){
  25.                 Position cur = queue[front];
  26.                 num--;
  27.                 front = (front + 1) % total;
  28.                 for(int m = 0; m < 4; m++){
  29.                     int x = p[m].x + cur.x;
  30.                     int y = p[m].y + cur.y;
  31.                     if(x >= 0 && x < gridSize && y >= 0 && y < *gridColSize && grid[x][y] == '1'){
  32.                         grid[x][y] = '0';
  33.                         queue[rear].x = x;
  34.                         queue[rear].y = y;
  35.                         num++;
  36.                         rear = (rear + 1) % total;
  37.                     }
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     return count;
  43. }

打开转盘锁

https://leetcode-cn.com/problems/open-the-lock/