Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 98875 Accepted Submission(s): 26807
//分析:题意是要恰好在t时间内到达,所以只能用dfs进行回溯搜索(bfs搜索的是最短路)。 //若 t-[abs(ex-sx)+abs(ey-sy)] 结果为非偶数(奇数),则无法在t步恰好到达; package 搜索; import java.util.Scanner; public class hdu_1010 { static char[][] map; static boolean flag; static boolean[][] vis; static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }; static int n, m, t; static int sx, sy, ex, ey; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { n = sc.nextInt(); m = sc.nextInt(); t = sc.nextInt(); if (n == 0 && m == 0 && t == 0) break; map = new char[n][m]; vis = new boolean[n][m]; for (int i = 0; i < n; i++) { String str = sc.next(); map[i] = str.toCharArray(); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == ‘S‘) { sx = i; sy = j; } if (map[i][j] == ‘D‘) { ex = i; ey = j; } } } if (t < Math.abs(ex - sx) + Math.abs(ey - sy)) { System.out.println("NO"); continue; } if ((t - Math.abs(ex - sx) + Math.abs(ey - sy)) % 2 != 0) { System.out.println("NO"); continue; } flag = false; vis[sx][sy]=true; //第一个点没标记WA了半天 dfs(sx, sy, 0); if (!flag) System.out.println("NO"); else System.out.println("YES"); } } private static void dfs(int x, int y, int time) { if (x == ex && y == ey && time == t) { //System.out.println(x+" "+y + " "+time); flag = true; return; } if (time >= t) //时间过了 return; for (int i = 0; i < 4; i++) { int next_x = x + dir[i][0]; int next_y = y + dir[i][1]; if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m || vis[next_x][next_y] == true || map[next_x][next_y] == ‘X‘) { continue; } vis[next_x][next_y] = true; dfs(next_x, next_y, time + 1); vis[next_x][next_y] = false; // 回溯 if (flag) return; // 找到了直接返回 } } }
原文:http://www.cnblogs.com/liyinggang/p/5255792.html