求帮忙关于：Number of island variant question

如下， 有没有好心人给个解题思路 TT
Input: 2D array, x coordinate, y coordinate

Output: number of adjacent element that is same as the arr[x Coordinate][y coordinate]

For example,
array:
[7,7,1,1]
[1,0,0,0]
[0,0,0,7]
[0,0,7,7]

x = 3
y = 3

Then array[3][3] = 7 which output should be 3 because
[7,7,1,1]
[1,0,0,0]
[0,0,0,7]
[0,0,7,7]
these three sevens.

是问给定坐标下的7在内周围连着的7吗？那从这个点出发dfs+visited set就可以吧？

Dearkano 发表于 2022-8-23 17:46
是问给定坐标下的7在内周围连着的7吗？那从这个点出发dfs+visited set就可以吧？

是的， array[3][3], which both 3 are from input, xCoordinate and yCoordinate. 我试着用bfs来做但是还是无法implement

微信用户_edc6079 发表于 2022-08-23 17:24:27
是的， array, which both 3 are from input, xCoordinate and yCoordinate. 我试着用bfs来做但是还是无法implement

为啥不能呢？visited set记录走过的地方，每从queue拿出一个点就向四个方向探索，如果是7并且不在visited里就入队并且res++

Dearkano 发表于 2022-8-23 20:42
为啥不能呢？visited set记录走过的地方，每从queue拿出一个点就向四个方向探索，如果是7并且不在visited ...

是的，我就是按你说的这样做的，我不知道为什么我的output不正确，可能我太菜了，帮帮我吧呜呜

能不能把有问题的代码贴上来，可以帮你看看

AppleFans 发表于 2022-8-24 02:38
能不能把有问题的代码贴上来，可以帮你看看

1. public static class location{
   
2.         int row;
   
3.         int col;
   
4.         public location(int row, int col){
   
5.             this.row = row;
   
6.             this.col = col;
   
7.         }
   
8.     }
   
9.     public static boolean isValid(Integer inputMap[][] , boolean visited[][], int currentRowLocation, int currentColLocation, int target){
   
10. 
    
11.         if ((currentRowLocation >= 0 && currentRowLocation < visited.length) &&
    
12.                 (currentColLocation >= 0 && currentColLocation < visited[0].length) &&
    
13.                 inputMap[currentRowLocation][currentColLocation] == target &&
    
14.                 !visited[currentRowLocation][currentColLocation]){
    
15.             return true;
    
16.         }else {
    
17.             return  false;
    
18.         }
    
19. 
    
20.     }
    
21.     public static void BreathFirstSearch(Integer[][] inputMap, boolean visited[][], int rowLocation, int colLocation){
    
22. 
    
23.         int row = inputMap.length;
    
24.         int col = inputMap[0].length;
    
25.         int target = inputMap[rowLocation][colLocation];
    
26.         Queue<location> queueForLocation = new LinkedList<>();
    
27.         queueForLocation.add(new location(rowLocation,colLocation));
    
28.         visited[rowLocation][colLocation] = true;
    
29. 
    
30.         while(!queueForLocation.isEmpty()){
    
31.             location currentLocation =  queueForLocation.peek();
    
32.             int x = currentLocation.row;
    
33.             int y = currentLocation.col;
    
34.             queueForLocation.remove();
    
35. 
    
36. //            System.out.println(inputMap[x][y] + " ");
    
37.             for(int i = 0; i < 4; i++){
    
38.                 int adjXCoordinate = x + i;
    
39.                 int adjYCoordinate = y + i;
    
40. 
    
41.                 if(isValid(inputMap, visited, adjXCoordinate, adjYCoordinate, target)){
    
42.                     queueForLocation.add(new location(adjXCoordinate, adjYCoordinate));
    
43.                     System.out.println(inputMap[adjXCoordinate][adjYCoordinate]);
    
44.                     visited[adjXCoordinate][adjYCoordinate] = true;
    
45. 
    
46.                 }
    
47.             }
    
48.         }
    
49.     }
    
50. 
    
51. // First testing input:
    
52.         // [1,2,3]
    
53.         // [4,5,6]
    
54.         // [2,1,1]
    
55.         // target = input[2][2] = 2
    
56.         // expected output = 4 -->
    
57. 
    
58. 
    

复制代码

感谢啊

微信用户_edc6079 发表于 2022-8-24 06:26
感谢啊

line 38 39, 为什么要 x + i, y + i? 你的i是从0到3，这样也没有访问上下左右四个neighbor啊。

上：[-1, 0] 下：[1, 0] 左：[0, -1] 右：[0, 1]