POJ 1198 双广+Hash

本文主要是介绍POJ 1198 双广+Hash，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

此题采用双广可从bfs的O(16^8)降低到O(2*16^4)；

坐标0-7，刚好3位存储， 需要24位存储四个坐标（x,y），也就是[0,2^24) 。

很好的一题。

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.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Live2667().solve();}
}class Live2667{InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;class Node implements Cloneable{class Point implements Comparable<Point>{int x ;int y ;@Overridepublic int compareTo(Point other) {if(x != other.x)  return x < other.x ? -1 : 1 ;else return y == other.y ?  0 : ( y < other.y ?  -1 : 1 ) ;}Point() {}@Overridepublic String toString() {return "Point [x=" + x + ", y=" + y + "]";}}Node(){for(int i = 0 ; i < 4 ; i++) p[i] = new Point() ;}Node setNode(){Node res = new Node() ;for(int i = 0 ; i < 4 ; i++){res.p[i].x = p[i].x ;res.p[i].y = p[i].y ;}res.step = step ;return res ;}Point[] p = new Point[4] ;int step ;int getHash(){Arrays.sort(p)  ;int res = 0 ;for(int i = 0 ; i < 4 ; i++){res |= (p[i].x << (6*i)) ;res |= (p[i].y << (6*i + 3)) ;}return res ;}boolean cango(){for(int i = 0 ; i < 4 ; i++){if(p[i].x < 0 || p[i].x >= 8 || p[i].y < 0 || p[i].y >= 8 )return false  ;}return true ;}boolean cover(int d){for(int i = 0 ; i < 4 ; i++){if(i == d) continue ;if(p[i].x == p[d].x && p[i].y == p[d].y) return true ;}return false ;}@Overridepublic String toString() {return "Node [p=" + Arrays.deepToString(p) + ", step=" + step + "]";}}Node start = new Node() ;Node end = new Node() ;Map<Integer , Integer> vis = new HashMap<Integer, Integer>() ; int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}} ;boolean bibfs(){vis.clear() ; Queue<Node> one = new LinkedList<Node>() ;Queue<Node> two = new LinkedList<Node>() ;one.add(start) ;two.add(end) ;vis.put( start.getHash() , 1) ;vis.put( end.getHash() , 2) ;while(! one.isEmpty() || ! two.isEmpty()){if(! one.isEmpty()){Node now = one.poll() ;if(now.step >= 4) continue ;for(int i = 0 ; i < 4 ; i++){for(int j = 0 ; j < 4 ; j++){Node next = now.setNode() ;next.p[i].x += dir[j][0] ;next.p[i].y += dir[j][1] ;if(! next.cango()) continue ;if(next.cover(i)){next.p[i].x += dir[j][0] ;next.p[i].y += dir[j][1] ;if(next.cango() && ! next.cover(i)){Integer key = next.getHash()  ;Integer value = vis.get( key ) ;if(value == null){vis.put(key , 1)  ;next.step++ ;one.add(next) ;}else if(value == 2) return true  ;}	}else{Integer key = next.getHash()  ;Integer value = vis.get( key ) ;if(value == null){vis.put(key , 1)  ;next.step++ ;one.add(next) ;}else if(value == 2) return true  ;}}}}if(! two.isEmpty()){Node now = two.poll() ;if(now.step >= 4) continue ;for(int i = 0 ; i < 4 ; i++){for(int j = 0 ; j < 4 ; j++){Node next = now.setNode() ;next.p[i].x += dir[j][0] ;next.p[i].y += dir[j][1] ;if(! next.cango()) continue ;if(next.cover(i)){next.p[i].x += dir[j][0] ;next.p[i].y += dir[j][1] ;if(next.cango() && ! next.cover(i)){Integer key = next.getHash()  ;Integer value = vis.get( key ) ;if(value == null){vis.put(key , 2)  ;next.step++ ;two.add(next) ;}else if(value == 1) return true  ;}	}else{Integer key = next.getHash()  ;Integer value = vis.get( key ) ;if(value == null){vis.put(key , 2)  ;next.step++ ;two.add(next) ;}else if(value == 1) return true  ;}}}}}return false ;}void solve(){while(in.hasNext()){start.step = end.step = 0 ;for(int i = 0 ; i < 4 ; i++){start.p[i].x = in.nextInt() - 1 ; start.p[i].y = in.nextInt() - 1 ; }for(int i = 0 ; i < 4 ; i++){end.p[i].x = in.nextInt() - 1 ; end.p[i].y = in.nextInt() - 1 ; }if(bibfs()) out.println("YES") ;else out.println("NO") ;//  out.flush() ; }out.flush() ; }}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());}}

这篇关于POJ 1198 双广+Hash的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---