黑车二面

楼主，我没觉得bfs有什么问题。。不知道你面试官怎么回事。。我祝福好运。
不过我想到一个问题是bfs 是不是要用一个visited 数组，如果visited了的东西，我们就不要再去visited了呀

如果不用BFS的话，我似乎想到一个解，复杂度应该没区别，但是更直观一些（如果面试官只看过标准答案的话是不容易再去想BFS？）

先找目标位置(x,y)的同行同列上下左右最远的四个X，如果都能找到的话，从目标行开始往上一行一行扫描，找到相距最远的一个X pair（假设允许一群O中间出现多余的X，否则找最近的跨越坐标x的pair），他们中间的interval不能有“.”且必须跟之前刚扫过那一行有intersect（如果有一个X位于坐标x，搜索结束）。同理再往下扫直到结束。如果所有行都扫完还没结束就是false


补充内容 (2018-11-27 15:57):
这样做的前提是在xy轴方向是简单变化的图形。。连通器那种复杂的形状只能遍历lol

1. import java.io.*;
   
2. import java.util.*;
   
3. 
   
4. class Solution {
   
5.     int[] dx = {0, 0, 1, -1};
   
6.     int[] dy = {1, -1, 0, 0};
   
7.     public boolean isCaptured(int x, int y, char[][] board) {
   
8.         if(x < 0 && y < 0 && x >= board.length && y >= board[0].length) {
   
9.             return false;
   
10.         }
    
11.         if(board[x][y] != 'O') {
    
12.             return false;
    
13.         }
    
14. 
    
15.         int rows = board.length;
    
16.         int cols = board[0].length;
    
17.         Set<Integer> visited = new HashSet<>();
    
18.         Deque<Integer> queue = new ArrayDeque<>();
    
19.         queue.offer(x * cols + y);
    
20.         visited.add(x * cols + y);
    
21.         while(!queue.isEmpty()) {
    
22.             int point = queue.poll();
    
23.             for(int i = 0; i < 4; i++) {
    
24.                 int px = point / cols + dx[i];
    
25.                 int py = point % cols + dy[i];
    
26.                 if(px < 0 || py < 0 || px >= rows || py >= cols) {
    
27.                     // not surrounded by 'X'
    
28.                     return false;
    
29.                 } else {
    
30.                     if(board[px][py] != 'X' && visited.add(px * cols + py)) {
    
31.                         queue.offer(px * cols + py);
    
32.                     }
    
33.                 }
    
34.             }
    
35.         }
    
36. 
    
37.         return true;
    
38.     }
    
39. 
    
40.     public static void main(String[] args) {
    
41.         Solution s = new Solution();
    
42.         char[][] board = {
    
43.             {'.', '.', 'X', 'X', '.'},
    
44.             {'.', 'X', 'O', 'O', 'X'},
    
45.             {'.', 'O', 'X', 'O', 'X'},
    
46.             {'X', 'X', 'O', 'X', 'O'},
    
47.             {'.', '.', 'X', 'X', 'O'}};
    
48.         char[][] board2 = {
    
49.             {'.', '.', 'X', 'X', '.'},
    
50.             {'.', 'X', '.', 'O', 'X'},
    
51.             {'X', '.', 'O', '.', 'X'},
    
52.             {'X', 'X', '.', 'X', '.'},
    
53.             {'.', '.', 'X', '.', '.'}};
    
54.         for(int i = 0; i < board.length; i++) {
    
55.             for(int j = 0; j < board[0].length; j++) {
    
56.                 System.out.print(s.isCaptured(i, j, board2) + ", ");
    
57.             }
    
58.             System.out.println();
    
59.         }
    
60.     }
    
61. }

复制代码

1. import java.io.*;
   
2. import java.util.*;
   
3. 
   
4. class Solution {
   
5.     int[] dx = {0, 0, 1, -1};
   
6.     int[] dy = {1, -1, 0, 0};
   
7.    
   
8.     public boolean isCaptured(int x, int y, char[][] board) {
   
9.         if(x < 0 && y < 0 && x >= board.length && y >= board[0].length) {
   
10.             return false;
    
11.         }
    
12.         if(board[x][y] != 'O') {
    
13.             return false;
    
14.         }
    
15. 
    
16.         // copy original data so that keep original board unchanged
    
17.         char[][] copy = new char[board.length][board[0].length];
    
18.         for(int i = 0; i < board.length; i++) {
    
19.             for(int j = 0; j  < board[0].length; j++) {
    
20.                 copy[i][j] = board[i][j];
    
21.             }
    
22.         }
    
23.         return helper(x, y, copy);
    
24.     }
    
25. 
    
26.     private boolean helper(int x, int y, char[][] board) {
    
27.         if(x < 0 || y < 0 || x >= board.length ||  y >= board[0].length) {
    
28.             return false;
    
29.         }
    
30.         if(board[x][y] =='X') {
    
31.             return true;
    
32.         }
    
33. 
    
34.         board[x][y] = 'X';
    
35.         boolean isCaptured = true;
    
36.         for(int i = 0; i < 4; i++) {
    
37.             isCaptured &= helper(x + dx[i], y + dy[i], board);
    
38.         }
    
39.         return isCaptured;
    
40.     }
    
41. 
    
42.     public static void main(String[] args) {
    
43.         Solution s = new Solution();
    
44.         char[][] board = {
    
45.             {'.', '.', 'X', 'X', '.'},
    
46.             {'.', 'X', 'O', 'O', 'X'},
    
47.             {'.', 'O', 'X', 'O', 'X'},
    
48.             {'X', 'X', 'O', 'X', 'O'},
    
49.             {'.', '.', 'X', 'X', 'O'}};
    
50.         char[][] board2 = {
    
51.             {'.', '.', 'X', 'X', '.'},
    
52.             {'.', 'X', '.', 'O', 'X'},
    
53.             {'X', '.', 'O', '.', 'X'},
    
54.             {'X', 'X', '.', 'X', '.'},
    
55.             {'.', '.', 'X', '.', '.'}};
    
56.         for(int i = 0; i < board.length; i++) {
    
57.             for(int j = 0; j < board[0].length; j++) {
    
58.                 System.out.print(s.isCaptured(i, j, board2) + ", ");
    
59.             }
    
60.             System.out.println();
    
61.         }
    
62.     }
    
63. }

复制代码

DFS还要修改棋盘，感觉没BFS好