Boggle

ProgrammingAlgorithm
Algorithm, Programming

Problem

http://algospot.com/judge/problem/read/BOGGLE

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
package com.sarojaba.algospot;
import java.util.Scanner;
/**
    * [http://algospot.com/judge/problem/read/BOGGLE](http://algospot.com/judge/problem/read/BOGGLE)
    * 
    * @author 준혁
    * 
    */
public class BOGGLE {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // test case
        int C = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < C; i++) {
            // board
            Board b = new Board(5, 5);
            for (int j = 0; j < 5; j++) {
                String line = scanner.nextLine();
                for (int k = 0; k < 5; k++) {
                    b.set(j, k, line.charAt(k));
                }
            }
            // words
            int N = Integer.parseInt(scanner.nextLine());
            for (int j = 0; j < N; j++) {
                String line = scanner.nextLine();
                String yn = b.search(line) ? "YES" : "NO";
                System.out.println(String.format("%s %s", line, yn));
            }
        }
        scanner.close();
    }
}
/**
    * implementation of boggle board
    * 
    * @author 준혁
    * 
    */
class Board {
    /**
        * board
        */
    private char[][] board;
    /**
        * constructor
        * 
        * @param r
        *            row
        * @param c
        *            col
        */
    public Board(int r, int c) {
        board = new char[r][c];
    }
    /**
        * setter
        * 
        * @param r
        *            index of row
        * @param c
        *            index of column
        * @param value
        */
    public void set(int r, int c, char value) {
        board[r][c] = value;
    }
    /**
        * exhaustive search
        * 
        * @param word
        * @return match
        */
    public boolean search(String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (search(i, j, word)) {
                    return true;
                }
            }
        }
        return false;
    }
    /**
        * 
        * @param r
        *            row
        * @param c
        *            col
        * @param word
        * @return match
        */
    private boolean search(int r, int c, String word) {
        // match
        if (word.isEmpty()) {
            return true;
        }
        // out of bound
        if (r < 0 || r > board.length - 1) {
            return false;
        }
        if (c < 0 || c > board[r].length - 1) {
            return false;
        }
        // not match
        if (board[r][c] != word.charAt(0)) {
            return false;
        }
        // recursive search
        String w = word.substring(1);
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if(i == 0 && j == 0) {
                    continue;
                }
                if (search(r + i, c + j, w)) {
                    return true;
                }
            }
        }
        return false;
    }
}

Comment

샘플 케이스만 만족시킨 답안이다. 완전 탐색이라 시간 초과에 걸린다.

Share Comments