Java 求助求助!!!样例本地测试过了,提交RE
查看原帖
Java 求助求助!!!样例本地测试过了,提交RE
909357
YuchaoM楼主2023/3/3 17:05

Java 求助求助!!!样例本地测试过了,提交RE

import java.io.*;


public class P1019单词接龙 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static PrintWriter out = new PrintWriter(bw);
    static StreamTokenizer st = new StreamTokenizer(br);

    static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    static String[] str = new String[30];
    static int[][] yc = new int[30][30];//记录i单词和它后面接j单词的最小重叠长度
    static int[] vis = new int[30];//某单词的使用次数
    static int n, an, ans;
    static char ch;//开头

    public static void main(String[] args) throws IOException {
        n = nextInt();
        for (int i = 0; i < n; i++) {
            str[i] = br.readLine();
        }
        ch = (char) br.read();

        //预处理所有单词两两之间的最小重叠长度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                yc[i][j] = mt(i, j);
            }
        }
        for (int i = 0; i < n; i++) {
            if (str[i].charAt(0) == ch) {
                vis[i]++;
                an = str[i].length();
                dfs(i);
                vis[i] = 0;//从新找开头
            }
        }
        System.out.println(ans);

    }

    private static void dfs(int i) {
        for (int j = 0; j < n; j++) {//继续接龙
            if (vis[j] == 2) continue;
            if (yc[i][j] == 0) continue;//没有重叠
            //相邻的两部分存在包含关系
            if (yc[i][j] == str[i].length() || yc[i][j] == str[j].length()) continue;
            an += str[j].length() - yc[i][j];//接上去
            vis[j]++;
            dfs(j);//继续接龙
            //回溯
            an -= str[j].length() - yc[i][j];
            vis[j]--;
        }
        ans = Math.max(ans, an);//最长的龙
    }

//    处理两个单词的最小重叠部分
    private static int mt(int x, int y) {
        int xlen = str[x].length(), ylen = str[y].length();
        int size = Math.min(xlen, ylen);
        for (int i = 1; i <= size; i++) {
            if (str[x].substring(xlen - i, xlen).equals(str[y].substring(0, i))) {
                return i;
            }
        }
        return 0;
    }
}

是我mt函数写错了吗

2023/3/3 17:05
加载中...