DouKaku?beta

challenge 文字列の八方向検索 

与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを
書いてください。
文字列の検索方向は八方全てで、また連続している（左右や上下の境界をまたがない）ものを
対象とします。出力は起点"ウ"の座標と方向のリストにしてください。

サンプル入力：

リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ

サンプル出力：

(2, 0), 左
(0, 1), 右
(0, 1), 下
(3, 1), 右
(4, 3), 左上

--
より一般には、任意の検索文字列への対応も考えてみてください。
post comment

Posted feedbacks - Java

素直に総当りで解いてみました。 enumをもうちょっと良い感じに使うと、さらに面白くなりそうな気もします。

  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
import java.util.ArrayList;
import java.util.List;

public class Sample99 {
    public enum Direction {
        左上, 上, 右上, 右, 右下, 下, 左下, 左,
    }

    private final String[] matrix_;

    public Sample99(String[] matrix) {
        matrix_ = matrix;
    }

    public AnswerData[] search(String str) {
        List<AnswerData> result = new ArrayList<AnswerData>();
        char[] input = str.toCharArray();
        for (int y = 0; y < matrix_.length; y++) {
            char[] cs = matrix_[y].toCharArray();
            for (int x = 0; x < cs.length; x++) {
                if (cs[x] != input[0]) continue;

                for (Direction d: Direction.values()) {
                    switch (d) {
                        case 左上:
                            if (x < input.length - 1) break;
                            if (y < input.length - 1) break;
                            if (search(input, x, y, -1, -1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 上:
                            if (y < input.length - 1) break;
                            if (search(input, x, y, 0, -1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 右上:
                            if (x > cs.length - input.length) break;
                            if (y < input.length - 1) break;
                            if (search(input, x, y, 1, -1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 右:
                            if (x > cs.length - input.length) break;
                            if (search(input, x, y, 1, 0)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 右下:
                            if (x > cs.length - input.length) break;
                            if (y > matrix_.length - input.length) break;
                            if (search(input, x, y, 1, 1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 下:
                            if (y > matrix_.length - input.length) break;
                            if (search(input, x, y, 0, 1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 左下:
                            if (x < input.length - 1) break;
                            if (y > matrix_.length - input.length) break;
                            if (search(input, x, y, -1, 1)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                        case 左:
                            if (x < input.length - 1) break;
                            if (search(input, x, y, -1, 0)) {
                                result.add(new AnswerData(x, y, d));
                            }
                            break;
                    }
                }
            }
        }
        return result.toArray(new AnswerData[0]);
    }
    private boolean search(char[] input, int x, int y, int dx, int dy) {
        for (int index = 1; index < input.length; index++) {
            if (matrix_[y + dy * index].charAt(x + dx * index) != input[index]) {
                return false;
            }
        }
        return true;
    }

    private static class AnswerData {
        public final int x;
        public final int y;
        public final Direction d;
        
        public AnswerData(int x, int y, Direction d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    public static void main(String[] args) {
        Sample99 s = new Sample99(new String[] {
                "リオウウリウ",
                "ウオリウオリ",
                "オリリオリウ",
                "リリオオウオ",
        });
        AnswerData[] datas = s.search("ウオリ");
        for (AnswerData d: datas) {
            System.out.format("(%d, %d), %s%n", d.x, d.y, d.d.name());
        }
    }
}

すいません、連投になってしまいますが短い版を投稿させていただきます。チェック手抜き版です。

 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
import java.util.ArrayList;
import java.util.List;

public class Sample99_2 {
    public enum Direction {
        左上(-1, -1),
        上(0, -1),
        右上(1, -1),
        右(1, 0),
        右下(1, 1),
        下(0, 1),
        左下(-1, 1),
        左(-1, 0);

        public final int dx_;
        public final int dy_;

        private Direction(int dx, int dy) {
            dx_ = dx;
            dy_ = dy;
        }
    }

    private final String[] matrix_;

    public Sample99_2(String[] matrix) {
        matrix_ = matrix;
    }

    public AnswerData[] search(String str) {
        List<AnswerData> result = new ArrayList<AnswerData>();
        char[] input = str.toCharArray();
        for (int y = 0; y < matrix_.length; y++) {
            for (int x = 0, maxX = matrix_[y].length(); x < maxX; x++) {
                for (Direction d: Direction.values()) {
                    if (search(input, x, y, d.dx_, d.dy_)) {
                        result.add(new AnswerData(x, y, d));
                    }
                }
            }
        }
        return result.toArray(new AnswerData[0]);
    }
    private boolean search(char[] input, int x, int y, int dx, int dy) {
        try {
            for (int index = 0; index < input.length; index++) {
                if (matrix_[y + dy * index].charAt(x + dx * index) != input[index]) {
                    return false;
                }
            }
            return true;
        } catch (IndexOutOfBoundsException ex) {
            return false;
        }
    }

    private static class AnswerData {
        public final int x;
        public final int y;
        public final Direction d;
        
        public AnswerData(int x, int y, Direction d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    public static void main(String[] args) {
        Sample99_2 s = new Sample99_2(new String[] {
                "リオウウリウ",
                "ウオリウオリ",
                "オリリオリウ",
                "リリオオウオ",
        });
        AnswerData[] datas = s.search("ウオリ");
        for (AnswerData d: datas) {
            System.out.format("(%d, %d), %s%n", d.x, d.y, d.d.name());
        }
    }
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]