pTtern in matrix

gistfile1.txt

package cccc;

public class PatternInMatrix {
	static boolean used[][];

	public static boolean findPattern(char[][] matrix, int nRow, int nCol, char[] pattern) {
		used = new boolean[nRow][nCol];

		for (int i = 0; i < nRow; i++)
			for (int j = 0; j < nCol; j++) {
				used[i][j] = false;
			}

		for (int i = 0; i < nRow; i++)
			for (int j = 0; j < nCol; j++) {
				if (matrix[i][j] == pattern[0])
					if (search(matrix, nRow, nCol, i, j, pattern, 0))
						return true;
			}

		return false;
	}

	private static boolean search(char[][] matrix, int nRow, int nCol, int row, int col, char[] pattern, int index) {
		System.out.println(row+ " " + col + " " + pattern[index] + used[row][col]);
		if (index == pattern.length - 1)
			return true;

		// check up
		if (row - 1 >= 0 && !used[row - 1][col]) {
			if (matrix[row - 1][col] == pattern[index + 1]) {
				used[row - 1][col] = true;
				if (search(matrix, nRow, nCol, row - 1, col, pattern, index + 1)) {
					return true;
				}
				used[row - 1][col] = false;
			}
		}

		// check down
		if (row + 1 < nRow && !used[row + 1][col]) {
			if (matrix[row + 1][col] == pattern[index + 1]) {
				used[row + 1][col] = true;
				if (search(matrix, nRow, nCol, row + 1, col, pattern, index + 1)) {
					return true;
				}
				used[row + 1][col] = false;
			}
		}

		// check left
		if (col - 1 >= 0 && !used[row][col - 1]) {
			if (matrix[row][col - 1] == pattern[index + 1]) {
				used[row][col - 1] = true;
				if (search(matrix, nRow, nCol, row, col - 1, pattern, index + 1)) {
					return true;
				}
				used[row][col - 1] = false;
			}
		}

		// check right
		if (col + 1 < nCol && !used[row][col + 1]) {
			if (matrix[row][col + 1] == pattern[index + 1]) {
				used[row][col + 1] = true;
				if (search(matrix, nRow, nCol, row, col + 1, pattern, index + 1)) {
					return true;
				}
				used[row][col + 1] = false;
			}
		}

		// check left up
		if (row - 1 >= 0 && col - 1 >= 0 && !used[row - 1][col - 1]) {
			if (matrix[row - 1][col - 1] == pattern[index + 1]) {
				used[row - 1][col - 1] = true;
				if (search(matrix, nRow, nCol, row - 1, col - 1, pattern, index + 1)) {
					return true;
				}
				used[row - 1][col - 1] = false;
			}
		}

		// check left down
		if (row + 1 < nRow && col - 1 >= 0 && !used[row + 1][col - 1]) {
			if (matrix[row + 1][col - 1] == pattern[index + 1]) {
				used[row + 1][col - 1] = true;
				if (search(matrix, nRow, nCol, row + 1, col - 1, pattern, index + 1)) {
					return true;
				}
				used[row + 1][col - 1] = false;
			}
		}

		// check right up
		if (row - 1 >= 0 && col + 1 < nCol && !used[row - 1][col + 1]) {
			if (matrix[row - 1][col + 1] == pattern[index + 1]) {
				used[row - 1][col + 1] = true;
				if (search(matrix, nRow, nCol, row - 1, col + 1, pattern, index + 1)) {
					return true;
				}
				used[row - 1][col + 1] = false;
			}
		}

		// check right down
		if (row + 1 < nRow && col + 1 < nCol && !used[row + 1][col + 1]) {
			if (matrix[row + 1][col + 1] == pattern[index + 1]) {
				used[row + 1][col + 1] = true;
				if (search(matrix, nRow, nCol, row + 1, col + 1, pattern, index + 1)) {
					return true;
				}
				used[row + 1][col + 1] = false;
			}
		}

		return false;
	}

	public static void main(String[] args) {
		char[][] m = { { 'A', 'C', 'P', 'R', 'C' }, { 'X', 'S', 'O', 'P', 'C' }, { 'V', 'O', 'V', 'N', 'I' },
				{ 'W', 'G', 'F', 'M', 'N' }, { 'Q', 'A', 'T', 'I', 'T' } };
//
//		A C P R C
//		X S O P C
//		V O V N I 
//		W G F M N 
//		Q A T I T
		
		
		
		String pattern = "MICROSOFT";
	 	pattern = "MIMICROSOFT";

		System.out.println(findPattern(m, 5, 5, pattern.toCharArray()));
	}

}