病毒隔离

class Solution {
    int n,m;
    int[][] g;
    boolean[][] vis;
    public int containVirus(int[][] isInfected){
        int res=0;
        g=isInfected;
        n=g.length;m=g[0].length;
        while(true){
            int cnt=find();//每次需要的挡板数量
            // System.out.println(cnt);
            if(cnt==0){
                break;
            }
            res+=cnt;
        }
        return res;
    }
    Set<Integer> set=new HashSet<>();
    List<int[]> path=new ArrayList<>();
    public int find(){
        int res=0;int cnt=0;

        vis=new boolean[n][m];
        // for(int i=0;i<n;i++){
        //     Arrays.fill(vis[i],false);    
        // }

        List<int[]> ps=new ArrayList<>();
        List<Set<Integer>> ss=new ArrayList<Set<Integer>>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(g[i][j]==1&&!vis[i][j]){
                    path.clear();set.clear();

                    // System.out.println("i"+i+"==="+"j"+j);

                    int t=dfs(i,j);//返回的是需要的挡板数

                    // System.out.println("需要的挡板数"+t);

                    if(set.size()>cnt){
                        res=t;
                        cnt=set.size();
                        // ps=path;
                        ps=new ArrayList<>(path);
                    }
                    // ss.add(set);
                    ss.add(new HashSet<>(set));
                }
            }
        }
        //将所有的选中的区域改为-
        for(int i=0;i<ps.size();i++){
            int[] node=ps.get(i);
            // System.out.println("修改"+node[0]+"==="+node[1]);
            g[node[0]][node[1]]=-1;
        }
        //病毒传播
        // for(int i=0;i<ss.size();i++){
        //     if(ss.get(i).size()!=cnt){
        //         for (int[] ints : ss.get(i)) {
        //             g[ints[0]][ints[1]]=1;
        //         }
        //     }
        // }

        for(int i=0;i<ss.size();i++){
            if(ss.get(i).size()!=cnt){
                for(Integer v:ss.get(i)){
                    int x=v/m;
                    int y=v%m;
                    g[x][y]=1;
                }
            }
        }

        return res;
    }
    int[] dx=new int[]{0,1,0,-1};
    int[] dy=new int[]{1,0,-1,0};
    public int dfs(int x,int y){
        vis[x][y]=true;
        path.add(new int[]{x,y});
        int res=0;
        for(int k=0;k<4;k++){
            int next_x=x+dx[k];
            int next_y=y+dy[k];
            if(next_x>=0&&next_x<n&&next_y>=0&&next_y<m){
                if(g[next_x][next_y]==0){
                    set.add(next_x*m+next_y);
                    res++;
                }else if(g[next_x][next_y]==1&&!vis[next_x][next_y]){
                    res+=dfs(next_x,next_y);
                }
            }
        }
        return res;
    }
} 

通过Set对二维数组进行去重的时候，将坐标点转为整数

开锁 BFS

class Solution {
    public int openLock(String[] deadends, String target) {
String start="0000";
        if(start.equals(target)){
            return 0;
        }
        //将所有的不能走的位置放入集合
        Set<String> set=new HashSet<>();
        for(String s:deadends){
            set.add(s);
        }
        if(set.contains(start)){
            return -1;
        }
        Queue<String> queue=new LinkedList<>();
        queue.offer(start);
        Map<String,Integer> dist=new HashMap<String,Integer>();
        dist.put(start,0);
        while(!queue.isEmpty()){
            String node=queue.poll();
            for(int k=0;k<4;k++){
                for(int j=-1;j<=1;j+=2){
                    String state=node;
                    StringBuilder sb=new StringBuilder(state);
                    sb.setCharAt(k,(char)((state.charAt(k)-'0'+j+10)%10+'0'));
                    state=new String(sb);
                    if(!set.contains(state)&&!dist.containsKey(state)){
                        dist.put(state,dist.get(node)+1);
                        if(state.equals(target)){
                            return dist.get(state);
                        }
                        queue.offer(state);
                    }
                }
            }
        }
        return -1;
    }
}