头像

XuanMichael




离线:5小时前


活动打卡代码 AcWing 1116. 马走日

XuanMichael
6小时前
import java.io.*;

public class Main {
    static final int N = 15;
    static int t, n, m, x, y, res, k;
    static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
    static boolean[][] status = new boolean[N][N];
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static void dfs(int x, int y, int s) {
        if (s == k) {
            ++res;
            return;
        }
        status[x][y] = true;
        int a, b;
        for (int i = 0; i < 8; ++i) {
            a = x + dir[i][0];
            b = y + dir[i][1];
            if (a > -1 && a < n && b > -1 && b < m && !status[a][b]) {
                dfs(a, b, s + 1);
            }
        }
        status[x][y] = false;
    }

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        t = (int)st.nval;
        while (t-- > 0) {
            st.nextToken();
            n = (int)st.nval;
            st.nextToken();
            m = (int)st.nval;
            k = n * m;
            st.nextToken();
            x = (int)st.nval;
            st.nextToken();
            y = (int)st.nval;
            dfs(x, y, 1);
            bw.write(res + "\n");
            res = 0;
        }
        bw.close();
    }
}


活动打卡代码 AcWing 1112. 迷宫

XuanMichael
7小时前
import java.io.*;

public class Main {
    static final int N = 110;
    static int k, n, sx, sy, tx, ty;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    static String[] input;
    static char[][] g = new char[N][N];
    static boolean[][] status;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static boolean dfs(int x, int y) {
        if (g[x][y] == '#') {
            return false;
        }
        if (x == tx && y == ty) {
            return true;
        }
        status[x][y] = true;
        int a, b;
        for (int i = 0; i < 4; ++i) {
            a = x + dx[i];
            b = y + dy[i];
            if (a > -1 && a < n && b > -1 && b < n && !status[a][b]) {
                if (dfs(a, b)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        // br = new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt")));
        k = Integer.parseInt(br.readLine().split(" ")[0]);
        String str;
        while (k-- > 0) {
            n = Integer.parseInt(br.readLine().split(" ")[0]);
            status = new boolean[N][N];
            for (int i = 0; i < n; ++i) {
                str = br.readLine();
                for (int j = 0; j < n; ++j) {
                    g[i][j] = str.charAt(j);
                }
            }
            input = br.readLine().split(" ");
            sx = Integer.parseInt(input[0]);
            sy = Integer.parseInt(input[1]);
            tx = Integer.parseInt(input[2]);
            ty = Integer.parseInt(input[3]);
            bw.write(dfs(sx, sy) ? "YES\n" : "NO\n");
        }
        bw.close();
    }
}


活动打卡代码 AcWing 9. 分组背包问题

import java.io.*;

public class Main {
    static final int N = 110;
    static int n, m;
    static int[] s = new int[N], f = new int[N];
    static int[][] v = new int[N][N], w = new int[N][N];
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        n = (int)st.nval;
        st.nextToken();
        m = (int)st.nval;
        for (int i = 1; i <= n; ++i) {
            st.nextToken();
            s[i] = (int)st.nval;
            for (int j = 1; j <= s[i]; ++j) {
                st.nextToken();
                v[i][j] = (int)st.nval;
                st.nextToken();
                w[i][j] = (int)st.nval;
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= 0; --j) {
                for (int k = 0; k <= s[i]; ++k) {
                    if (j >= v[i][k]) {
                        f[j] = Math.max(f[j], f[j - v[i][k]] + w[i][k]);
                    }
                }
            }
        }
        bw.write(f[m] + "");
        bw.close();
    }
}



import java.io.*;

public class Main {
    static final int N = 110;
    static int k, n, h;
    static int[] a = new int[N], f = new int[N];
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        k = (int)st.nval;
        int res;
        while (k-- > 0) {
            st.nextToken();
            n = (int)st.nval;
            for (int i = 1; i <= n; ++i) {
                st.nextToken();
                a[i] = (int)st.nval;
            }
            res = 0;
            for (int i = 1; i <= n; ++i) {
                f[i] = 1;
                for (int j = 1; j < i; ++j) {
                    if (a[j] < a[i]) {
                        f[i] = Math.max(f[i], f[j] + 1);
                    }
                }
                res = Math.max(res, f[i]);
            }
            for (int i = 1; i <= n; ++i) {
                f[i] = 1;
                for (int j = 1; j < i; ++j) {
                    if (a[j] > a[i]) {
                        f[i] = Math.max(f[i], f[j] + 1);
                    }
                }
                res = Math.max(res, f[i]);
            }
            bw.write(res + "\n");
        }
        bw.close();
    }
}


活动打卡代码 AcWing 1018. 最低通行费

import java.io.*;

public class Main {
    static final int N = 110, INF = (int)1e9;
    static int n;
    static int[][] w = new int[N][N], f = new int[N][N];
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        n = (int)st.nval;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                st.nextToken();
                w[i][j] = (int)st.nval;
            }
        }
        for (int i = 0; i <= n; ++i) {
            f[i][0] = f[0][i] = INF;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == 1 && j == 1) {
                    f[i][j] = w[i][j];
                } else {
                    f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + w[i][j];
                }
            }
        }
        bw.write(f[n][n] + "");
        bw.close();
    }
}


活动打卡代码 AcWing 1015. 摘花生

import java.io.*;

public class Main {
    static final int N = 110;
    static int t, n, m, x;
    static int[][] w = new int[N][N], f = new int[N][N];
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        t = (int)st.nval;
        while (t-- > 0) {
            st.nextToken();
            n = (int)st.nval;
            st.nextToken();
            m = (int)st.nval;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    st.nextToken();
                    w[i][j] = (int)st.nval;
                }
            }
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    f[i][j] = Math.max(f[i][j - 1], f[i - 1][j]) + w[i][j];
                }
            }
            bw.write(f[n][m] + "\n");
        }
        bw.close();
    }
}



import java.io.*;

public class Main {
    static final int N = 15;
    static int n;
    static int[] path = new int[N];
    static boolean[] status = new boolean[N];
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static void dfs(int u) throws IOException {
        if (u == n) {
            for (int i = 0; i < n; ++i) {
                bw.write(path[i] + " ");
            }
            bw.write("\n");
            return;
        }
        for (int i = 1; i <= n; ++i) {
            if (status[i]) {
                continue;
            }
            path[u] = i;
            status[i] = true;
            dfs(u + 1);
            status[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        n = (int)st.nval;
        dfs(0);
        bw.close();
    }
}



import java.io.*;

public class Main {
    static final int N = 20;
    static int n;
    static boolean[] status = new boolean[N];
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static void dfs(int u) throws IOException {
        if (u == n) {
            for (int i = 0; i < n; ++i) {
                if (status[i]) {
                    bw.write(i + 1 + " ");
                }
            }
            bw.write("\n");
            return;
        }
        dfs(u + 1);
        status[u] = true;
        dfs(u + 1);
        status[u] = false;
    }

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        n = (int)st.nval;
        dfs(0);
        bw.close();
    }
}

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 20;
    static int n;
    static boolean[] status = new boolean[N];
    static ArrayList<Integer> cur;
    static ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static void dfs(int u) throws IOException {
        if (u == n) {
            cur = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                if (status[i]) {
                    cur.add(i + 1);
                }
            }
            res.add(cur);
            return;
        }
        dfs(u + 1);
        status[u] = true;
        dfs(u + 1);
        status[u] = false;
    }

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        n = (int)st.nval;
        dfs(0);
        for (int i = 0; i < res.size(); ++i) {
            for (int x : res.get(i)) {
                bw.write(x + " ");
            }
            bw.write("\n");
        }
        bw.close();
    }
}


活动打卡代码 AcWing 901. 滑雪

import java.io.*;

public class Main {
    static final int N = 310;
    static int n, m;
    static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    static int[][] h = new int[N][N], f = new int[N][N];
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int dp(int x, int y) {
        if (f[x][y] != -1) {
            return f[x][y];
        }
        f[x][y] = 1;
        int a, b;
        for (int i = 0; i < 4; ++i) {
            a = x + dx[i];
            b = y + dy[i];
            if (a > 0 && a <= n && b > 0 && b <= m && h[a][b] < h[x][y]) {
                f[x][y] = Math.max(f[x][y], dp(a, b) + 1);
            }
        }
        return f[x][y];
    }

    public static void main(String[] args) throws IOException {
        // st = new StreamTokenizer(
        // new BufferedReader(new InputStreamReader(new FileInputStream("/Users/huangweixuan/testdata.txt"))));
        st.nextToken();
        n = (int)st.nval;
        st.nextToken();
        m = (int)st.nval;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                st.nextToken();
                h[i][j] = (int)st.nval;
                f[i][j] = -1;
            }
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                res = Math.max(res, dp(i, j));
            }
        }
        bw.write(res + "");
        bw.close();
    }
}



需要重写 equals 和 hashCode 两个方法

import java.util.*;

public class Main {
    static HashMap<Node, Integer> hm = new HashMap<>();

    static class Node {
        int x, y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Node) {
                Node t = (Node)obj;
                return t.x == x && t.y == y;
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}