InfiBeam.java

/*
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Input Format:

The first line of the input will have N and M (separated by space) for the size of the board. Next M lines will have N letters of the board each.
The last line will have word to search.

Output Format:

‘True’ or ‘False’ based on whether the word is there in the matrix or not

Example:
Input -
4 3
ABCE
SFCS
ADEE
ABCCED

Output - True
*/

import java.io.*;
import java.util.*;

public class InfiBeam {
  
	private static final char visited = '#';
	
	public static boolean dfs(char[][] input, String word, int s, int r, int c) {
		boolean found = false;
		if(s==word.length())
			return true;
		
		if(r<0 || c<0 || r>input.length-1 || c >input[0].length-1)
			return false;
		
		if(input[r][c] == word.charAt(s)) {
				input[r][c] = visited;
				found = dfs(input,word,s+1,r+1,c) ||
						dfs(input,word,s+1,r-1,c) ||
						dfs(input,word,s+1,r,c+1) ||
						dfs(input,word,s+1,r,c-1);		
		}
		return found;
	}
	public static String containsWord(char[][] input, String word) {
		String found = "False";
		for(int i=0; i<input.length;i++) {
			for(int j=0; j < input[i].length; j++) {
				if(input[i][j] == word.charAt(0)) {
					if(dfs(input,word,0,i,j))
						return "True";
				}
			}
		}
		return found;
	}
	
	public static void main(String[] args){
		Scan scan  = new Scan();
		
		char[][] input = new char[3][3];
		int num_char = scan.nextInt();
		int lines = scan.nextInt();
		
		input = new char[lines][num_char];
		
		for(int i=0; i<lines; i++) {
			String line = scan.next();
			for(int j=0; j < num_char; j++) {
				input[i][j] = line.charAt(j);
			}
		}
		String word = scan.next();
		System.out.println(containsWord(input,word));
			
	}
}
//templete
class Scan {
    BufferedReader br;
    StringTokenizer st;
 
    public Scan() {
            br = new BufferedReader(new InputStreamReader(System.in));
    }
 
    boolean hasNext(){
            if(st.hasMoreElements())
                    return true;
            try {
                    st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                    e.printStackTrace();
            }
            return st.hasMoreTokens();
    }
    String next() {
            while (st == null || !st.hasMoreElements()) {
                    try {
                            st = new StringTokenizer(br.readLine());
                    } catch (Exception e) {
                            e.printStackTrace();
                    }
            }
            return st.nextToken().trim();
    }
 
    int nextInt() {
            return Integer.parseInt(next());
    }
 
    int nextint() {
            return Integer.parseInt(next());
    }
 
    double nextDouble() {
            return Double.parseDouble(next());
    }
 
    String nextLine(){
            String str = "";
            try {
                    str = br.readLine();
            } catch (IOException e) {
                    e.printStackTrace();
            }
            return str;
    }
 
    public long nextLong() {
            return Long.parseLong(next());
    }
 
}