algorithm wheres waldort - andstudy/forge GitHub Wiki

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  
  
  public class Searcher {
  	
  	private char [][] crossSource;
  	
  	public Searcher(String[] sourceLine,int height,int width) {
  		initCrossSrouce(sourceLine,height,width);
  	}
  
  	private void initCrossSrouce(String[] sourceLines,int height,int width) {
  		crossSource = new char[height][width];
  		for(int i=0;i<sourceLines.length;i++){
  			String curLine = sourceLines[i];
  			for(int j=0;j<curLine.length();j++){
  				crossSource[i][j] = curLine.charAt(j);
  			}
  		}
  	}
  
  	public boolean isStartWith(String source, String match) {
  		source = source.toLowerCase();
  		match = match.toLowerCase();
  		return source.startsWith(match);
  	}
  
  	public String devideTop(int y, int x) {
  		StringBuilder builder = new StringBuilder();
  		for(int i=y;i>=0;i--){
  			builder.append(crossSource[i][x]);
  		}
  		
  		return builder.toString().toLowerCase();
  	}
  	
  	public int getWidth(){
  		if(crossSource.length < 1){
  			return 0;
  		}
  		return crossSource[0].length;
  	}
  	
  	public int getHeight(){
  		return crossSource.length;
  	}
  
  	public String devideDown(int y, int x) {
  		StringBuilder builder = new StringBuilder();
  		for(int i=y;i<getHeight();i++){
  			builder.append(crossSource[i][x]);
  		}
  		return builder.toString().toLowerCase();
  	}
  
  	public String devideLeft(int y, int x) {
  		StringBuilder builder = new StringBuilder();
  		for(int i=x;i>=0;i--){
  			builder.append(crossSource[y][i]);
  		}
  		return builder.toString().toLowerCase();
  	}
  	public String devideRight(int y, int x) {
  		StringBuilder builder = new StringBuilder();
  		for(int i=x;i<getWidth();i++){
  			builder.append(crossSource[y][i]);
  		}
  		return builder.toString().toLowerCase();
  	}
  
  	public String devideUpLeft(int y, int x) {
  		StringBuilder builder = new StringBuilder();
  		for(int i=y,j=x;i>=0 && j>=0;i--,j--){
  				builder.append(crossSource[i][j]);
  		}
  		return builder.toString().toLowerCase();
  	}
  
  	public String devideUpRight(int y, int x) {
  		StringBuilder builder = new StringBuilder();
  		for(int i=y,j=x;i>=0 && j<getWidth();i--,j++){
  			builder.append(crossSource[i][j]);
  		}
  		return builder.toString().toLowerCase();
  	}
  
  	public String devideDownLeft(int y, int x) {
  		StringBuilder builder = new StringBuilder();
  		for(int i=y,j=x;i<getHeight() && j>=0;i++,j--){
  			builder.append(crossSource[i][j]);
  		}
  		return builder.toString().toLowerCase();
  	}
  
  	public String devideDownRight(int y, int x) {
  		StringBuilder builder = new StringBuilder();
  		for(int i=y,j=x;i<getHeight() && j<getWidth();i++,j++){
  			builder.append(crossSource[i][j]);
  		}
  		return builder.toString().toLowerCase();
  	}
  
  	public Point searchString(String match) {
  		for(int i=0;i<getWidth();i++){
  			for(int j=0; j<getHeight();j++){
  				if(isStartWith(devideTop(i, j), match) 
  					|| isStartWith(devideDown(i, j), match)
  					|| isStartWith(devideLeft(i, j), match)
  					|| isStartWith(devideRight(i, j), match)
  					|| isStartWith(devideUpLeft(i, j), match)
  					|| isStartWith(devideUpRight(i, j), match)
  					|| isStartWith(devideDownLeft(i, j), match)
  					|| isStartWith(devideDownRight(i, j), match) ){
  					return new Point(i+1,j+1);
  				}
  			}
  		}
  		return null;
  	}
  	
  	
  	public static void main(String[] args) throws NumberFormatException, IOException {
  		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  		int cases = Integer.parseInt(reader.readLine().trim());
  		ArrayList<String> results = new ArrayList<String>();
  		for(int i=0;i<cases;i++){
  			reader.readLine();
  			String line = reader.readLine();
  			String[] split = line.split(" ");
  			int height = Integer.parseInt(split[0]);
  			int width = Integer.parseInt(split[1]);
  			String [] lines = new String[height];
  			for(int j=0;j<height;j++){
  				lines[j] = reader.readLine();
  			}
  			
  			int numToFind = Integer.parseInt(reader.readLine().trim());
  			Searcher searcher = new Searcher(lines,height,width);
  			for(int j=0;j<numToFind;j++){
  				Point result  = searcher.searchString(reader.readLine().trim());
  				results.add(result.toString());
  			}
  			results.add("");
  		}
  		
  		for(String line : results){
  			System.out.println(line);
  		}
  	}
  }

  public class Point {
  	@Override
  	public boolean equals(Object obj) {
  		if (obj instanceof Point) {
  			Point pnt = (Point) obj;
  			return this.x == pnt.getX() && this.y == pnt.getY();
  		}else{
  			return false;
  		}
  	}
  
  	private int x;
  	private int y;
  	
  	public Point(int y , int x){
  		this.x = x;
  		this.y = y;
  	}
  	
  	public String toString(){
  		return y+" "+x;
  	}
  
  	public int getX() {
  		return x;
  	}
  
  	public int getY() {
  		return y;
  	}
  }

  import junit.framework.TestCase;
  
  
  public class SearcherTest extends TestCase {
  	Searcher searcher ;
  	private String [] crossSource = {
  			"abcDEFGhigg",
  			"hEbkWalDork",
  			"FtyAwaldORm",
  			"FtsimrLqsrc",
  			"byoArBeDeyv",
  			"Klcbqwikomk",
  			"strEBGadhrb",
  			"yUiqlxcnBjf"
  	};
  	@Override
  	protected void setUp() throws Exception {
  		searcher = new Searcher(crossSource,8,11);
  		super.setUp();
  	}
  	public void testLineMatch(){
  		String source = "abcdefg";
  		assertTrue(searcher.isStartWith(source,"abcdef"));
  		assertTrue(searcher.isStartWith(source,"Abcdef"));
  		assertFalse(searcher.isStartWith(source,"bcdefg"));
  		assertFalse(searcher.isStartWith(source,"Bcdefg"));
  	}
  	
  	public void testDevideTop(){
  		
  		assertEquals("akd", searcher.devideTop(2,3));
  		assertEquals("a", searcher.devideTop(0,0));
  		assertEquals("cmkg", searcher.devideTop(3,10));
  	}
  	public void testDevideDown(){
  		assertEquals("ahffbksy", searcher.devideDown(0,0));
  		assertEquals("bl", searcher.devideDown(6,4));
  	}
  	public void testDevideLeft(){
  		assertEquals("eh", searcher.devideLeft(1,1));
  		assertEquals("erts", searcher.devideLeft(6,3));
  	}
  	public void testDevideRight(){
  		assertEquals("ldork", searcher.devideRight(1, 6));
  		assertEquals("jf", searcher.devideRight(7, 9));
  	}
  	public void testDevideUpLeft(){
  		assertEquals("ea", searcher.devideUpLeft(1,1));
  		assertEquals("th", searcher.devideUpLeft(2,1));
  	}
  
  	public void testDevideUpRight(){
  		assertEquals("di", searcher.devideUpRight(1,7));
  		assertEquals("srk", searcher.devideUpRight(3,8));
  		
  	}
  	public void testDevideDownLeft(){
  		assertEquals("ef", searcher.devideDownLeft(1,1));
  		assertEquals("btf", searcher.devideDownLeft(1,2));
  	}
  	public void testDevideDownRight(){
  		assertEquals("irm", searcher.devideDownRight(0,8));
  	}
  	
  	public void testSearchString(){
  		assertEquals(new Point(2,5), searcher.searchString("Waldorf"));
  		assertEquals(new Point(2, 3), searcher.searchString("Bambi"));
  		assertEquals(new Point(1, 2), searcher.searchString("Betty"));
  		assertEquals(new Point(7, 8), searcher.searchString("Dagbert"));
  	}
  }