2 D配列で指定したシーケンスが存在するかどうかを検索

	//     word            
	private boolean checkExist(Map<Character, Unit> map, String word, int index) {
		if(index >= word.length() - 1)
			return true;
		
		char ch = word.charAt(index);
		Unit unit = map.get(ch);
		char nextCh = word.charAt(index + 1);
		Unit nextUnit = map.get(nextCh);
		
		//         map ，             ，    false
		if(unit == null || nextUnit == null)
			return false;
  
		//            
		for(Point p : unit.getPoints()) {
			if(p.isUsed())
				continue;
			//        ，              ，        
			p.setUsed(true);
			for(Point next : nextUnit.getPoints()) {
				//       ，     
				if(next.isUsed())
					continue;
				if(!p.adjacent(next))
					continue;
				//           ，  word         ，       
				boolean ret = checkExist(map, word, index + 1);
				//   true。     word       ，      			
				if(ret) 
					return true;
			}
			p.setUsed(false);
		}
		
		//                       ，  false，             
		return false;
	}

class Element {
private char ch;
private int index;
private int nextIndex;
}

	public boolean exist(char[][] board, String word) {
		//    map
        int length = word.length();
        Stack stack = new Stack(length);
        List<Point> head = indexMap.get(word.charAt(0));
        if(head == null)
        	return false;
        for(int i = 0 ; i < head.size() ; ++ i) {
        	stack.push(new Element(word.charAt(0), i));
        	head.get(i).setUsed(true);
        	while(stack.getTop() > 0) {
        		int index = stack.getTop() - 1;
        		if(index == length - 1)
        			return true;
        		Element top = stack.top();
        		Element next = getNextElement(indexMap, word, index, top);
        		if(next == null) {
        			Element e = stack.pop();
        			indexMap.get(e.getChar()).get(e.getIndex()).setUsed(false);
        		}
        		else {
        			stack.push(next);
        		}
        	}
        }
        return false;
	}
	
	//                   
	private Element getNextElement(Map<Character, List<Point>> map, String word, int index, Element prev) {
		if(index >= word.length() - 1)
			return null;
		
		char first = word.charAt(index);
		char second = word.charAt(index + 1);
		
		List<Point> cur = map.get(first);
		List<Point> next = map.get(second);
		if(cur == null || next == null)
			return null;
		
		Point point = cur.get(prev.getIndex());
		int size = next.size();
		//              
		for(int i = prev.getNextIndex() + 1 ; i < size ; ++ i) {
			Point nextPoint = next.get(i);
			if(nextPoint.isUsed())
				continue;
			if(point.adjacent(nextPoint)) {
				nextPoint.setUsed(true);
				prev.setNextIndex(i);
				return new Element(second, i);
			}
		}
		return null;
	}