hdu1010 奇偶剪枝

本文主要是介绍hdu1010 奇偶剪枝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

恰好t时间到达

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new HDU1010().solve();}
}class HDU1010 {InputReader in = new InputReader(System.in);PrintWriter out = new PrintWriter(System.out);final int N = 10 ;int n , m  , upStep ;boolean[][] vis = new boolean[N][N] ;char[][] wall = new char[N][N] ;int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}} ;boolean can(int x , int y){return 0 <= x && x < n && 0 <= y && y < m ;}int sx , sy , ex , ey ;void solve() {for(;;){n = in.nextInt() ;m = in.nextInt() ;upStep = in.nextInt() ;if(n == 0 && m == 0 && upStep == 0) break ;for(int i = 0 ; i < n ; i++) wall[i] = in.next().toCharArray() ;for(int i = 0 ; i < n ; i++){for(int j = 0 ; j < m ; j++){if(wall[i][j] == 'S'){sx = i ;  sy = j ;}else if(wall[i][j] == 'D'){ex = i ;  ey = j ;}}}for(int i = 0 ; i < n ; i++) Arrays.fill(vis[i] , false) ;vis[sx][sy] = true ;if(dfs(sx, sy, 0)) out.println("YES") ;else out.println("NO") ;} 	out.flush();}boolean dfs(int x , int y , int step){if(step > upStep)  return false ;if(x == ex && y == ey && step == upStep) return true ;if((upStep - step) % 2 != (Math.abs(x-ex) + Math.abs(y-ey)) % 2) return false ;for(int i = 0 ; i < 4 ; i++){int nx = x + dir[i][0] ;int ny = y + dir[i][1] ; if(can(nx, ny) && wall[nx][ny] != 'X' && ! vis[nx][ny]){vis[nx][ny] = true ;if(dfs(nx, ny, step+1)) return true ;vis[nx][ny] = false ;}}return false ;}}class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = new StringTokenizer("");}private void eat(String s) {tokenizer = new StringTokenizer(s);}public String nextLine() {try {return reader.readLine();} catch (Exception e) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String s = nextLine();if (s == null)return false;eat(s);}return true;}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}

这篇关于hdu1010 奇偶剪枝的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---