1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class solution{
    public List<List<Integer>> subsets(int[] nums){
        List<List<Integer>> res=new ArrayList<>();
        backtrack(nums,0,new ArrayList<>(),res);
        return res;
    }

    private void backtrack(int[] nums,int start,List<Integer> path,List<List<Integer>> res){
        res.add(new ArrayList<>(path));

        for(int i=path;i<nums.length;i++){
            path.add(nums[i]);
            backtrack(nums,i+1,path,res);
            path.remove(path.size()-1);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution{
    int[] dx={1,0,0,1};
    int[] dy={0,1,-1,0};
    public int[][] floodFill(int[][] image,int sr,int sc,int color){
        int currColor=image[sr][sc];
        if(curColor==color){
            return image;
        }
        int n=image.length,m=image[0].length;
        Queue<int[]> queue=new LinkedList<int[]>();
        queue.offer(new int[]{sr,sc});
        image[sr][sc]=color;
        while(!queue.isEmpty()){
            int[] cell=queue.poll();
            int x=cell[0],y=cell[1];
            for(int i=0;i<4;i++){
                int mx=x+dx[i],my=y+dy[i];
                if(mx>=0&&my>=0&&mx<=n&&my<=m&&image[mx][my]==curColor){
                    queue.offer(new int[]{mx,my});
                    image[mx][my]=color;
                }
            }
        }
        return image;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution{
    int[] dx={1,0,0,-1};
    int[] dy={0,1,-1,0};
    public int[][] floodFill(int[][] image,int sr,int sc,int color){
        int curColor=image[sr][sc];
        if(curColor!=color){
            dfs(image,sr,sc,curColor,color);
        }
        return image;
    }
    public void dfs(int[][] image,int x,int y,int curColor,int color){
        if(image[x][y]==curColor){
            image[x][y]=color;
            for(int i=0;i<4;i++){
                int mx=x+dx[i],my=y+dy[i];
                if(mx>=0&&mx<=image.length&&my>=0&&my<=image[0].length){
                    dfs(image,mx,my,curColor,color);
                }
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution{
    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};
    public int islandPerimeter(int[][] grid){
        int n=grid.length,int m=grid[0].length;
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    ans+=dfs(i,j,grid,n,m);
                }
            }
        }
        return ans;
    }
    public int dfs(int x,int y,int[][] grid,int n,int m){
        if(x<0||x>=n||y<0||y>m||grid[x][y]==0){
            return 1;
        }
        if(grid[x][y]==2){
            return 0;
        }
        grid[x][y]=2;
        int res=0;
        for(int i=0;i<4;i++){
            int tx=x+dx[i];
            int ty=y+dy[i];
            res+=dfs(tx,ty,grid,n,m);
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public class Main{
    static int[] digitSum;
    static void calcDigitSum(int maxVal){
        digitSum=new int[maxVal];
        for(int i=0;i<maxVal;i++){
            int num=i,tmp=0;
            while(num>0){
                tmp+=num%10;
                num/=10;
            }
            digitSum[i]=tmp;
        }
    }
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int m=scanner.nextInt(),n=scanner.nextInt(),k=scanner.nextInt();
        scanner.close();
        if(m==0||n==0){
            System.out.println(0);
            return;
        }
        calcDisitSum(Math.max(m,n));
        int[][] direct={{-1,0},{1,0},{0,-1},{0,1}};
        Set<Integer> visited=new HashSet<>();
        Queue<Integer> queue=new LinkedList<>();
        queue.add(0);
        visited.add(0);
        int res=1;
        while(!queue.isEmpty()){
            int num=queue.poll();
            int x=num/n,y=num%n;
            for(int[] d:direct){
                int newX=x+d[0],newY=y+d[1];
                int newNum=newX*newY;
                if(newX<0||newY<0||newX>=m||newY>=n||visited.contains(newNum)){
                    continue;
                }
                if(digitSum[newX]+digitSum[newY]>k){
                    continue;
                }
                res++;
                queue.add(newNum);
                visited.add(newNum);
            }
        }
        System.out.println(res);
    }
}