返回题解分享
讨论 / 题解分享/ 帖子详情

小红与字符串矩阵 - 题解

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;
}


}
0 回复 0 转发 0 喜欢 3 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!