4 条题解

  • 0
    @ 2024-4-7 10:25:02

    import java.io.*;

    public class Main { public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public static int n; public static int m; public static String[][] map; public static long cnt = 0; public static boolean[][] isuse; public static String[] t = { "t", "e", "n", "c", "e", "n", "t" }; public static int[][] way = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public static void main(String[] args) throws IOException {
    	// TODO Auto-generated method stub
    	String[] s = in.readLine().split(" ");
    	n = Integer.parseInt(s[0]);
    	m = Integer.parseInt(s[1]);
    	map = new String[n][m];
    	isuse = new boolean[n][m];
    	for (int i = 0; i < n; i++) {
    		map[i] = in.readLine().split("");
    	}
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (map[i][j].equals("t")) {//剪枝,从t开始走
    				dfs(i, j, 1, map[i][j]);
    			}
    		}
    	}
    	System.out.println(cnt);
    }
    
    public static void dfs(int x, int y, int len, String ans) {
    	if (ans.equals("tencent")) {
    		cnt++;
    		return;
    	}
    	if (len > 6)//剪枝
    		return;
    	for (int i = 0; i < 4; i++) {//枚举四个方向
    		int xx = x + way[i][0];
    		int yy = y + way[i][1];
    		//剪枝,下一步要走的和期望要得到的字符一样才走
    		if (check(xx, yy) && map[xx][yy].equals(t[len])) {
    			isuse[xx][yy] = true;//走过就不走了
    			dfs(xx, yy, len + 1, ans + map[xx][yy]);
    			isuse[xx][yy] = false;//回溯
    		}
    	}
    }
    
    public static boolean check(int x, int y) {//判断是否在边界内,并且可走
    	return x >= 0 && x < n && y >= 0 && y < m && isuse[x][y] == false;
    }
    

    }

    信息

    ID
    81
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    102
    已通过
    22
    上传者