蚂蚁24年秋招-工程研发-2024-09-19

1

2

// Description: 蚂蚁24年秋招-工程研发-0919-编程第2题
// Accept: 100%
// Date: 2024/09/19

package main;

import java.util.Scanner;

public class Main {

    private static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int T = in.nextInt();
            in.nextLine();
            while (T-- > 0) {
                in.nextLine();
                String s = in.nextLine();

                if (s.length() <= 1 || !isPalindrome(s)) {
                    System.out.println(0);
                    continue;
                }

                boolean same = true;
                char c = s.charAt(0);
                for (int i = 1; i < s.length(); i++) {
                    if (s.charAt(i) != c) {
                        System.out.println(1);
                        same = false;
                        break;
                    }
                }
                if (same) {
                    System.out.println(s.length() - 1);
                }
            }
        }
    }
}

/*
1
4
abba
输出：1
 */

3

// Description: 蚂蚁24年秋招-工程研发-0919-编程第3题
// Accept: 54%
// Date: 2024/09/19

package main;

import java.util.Scanner;

public class Main {
    private static final int N = 4;
    private static final int[][] grid = new int[N][N];
    private static final boolean[][] visited = new boolean[N][N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    grid[i][j] = in.nextInt();
                }
            }

            int res = 0;
            while (true) {
                if (checkZeroConnectivity()) {
                    System.out.println(res);
                    break;
                }
                int[] max_ij = getMax();
                grid[max_ij[0]][max_ij[1]] = 0;
                ++res;
            }
        }
    }

    private static int[] getMax() {
        int max = grid[0][0], max_i = 0, max_j = 0;

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (grid[i][j] > max) {
                    max = grid[i][j];
                    max_i = i;
                    max_j = j;
                }
            }
        }

        return new int[]{max_i, max_j};
    }

    private static boolean checkZeroConnectivity() {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                visited[i][j] = false;
            }
        }

        // 寻找第一个0的位置
        boolean foundZero = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 0) {
                    dfs(i, j);
                    foundZero = true;
                    break;
                }
            }
            if (foundZero) {
                break;
            }
        }

        // 检查是否所有0都被访问过
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 0 && !visited[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void dfs(int x, int y) {
        // 四个方向：上下左右
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        visited[x][y] = true;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (isValid(nx, ny) && grid[nx][ny] == 0 && !visited[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }

    private static boolean isValid(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}



/*

输入：
1 2 0 0
4 3 0 0
5 6 7 8
0 0 0 0
输出：1

1 2 0 0
4 3 0 0
5 6 7 0
0 0 0 0
输出：0
 */