4 条题解
-
0
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
- 上传者