0

私はJavaで次のような2D配列を持っています:

int 2d_arr[5][5];

たとえば、次のようなボードを考えてみましょう。

1 1 1 1 1
0 1 1 1 1
1 1 2 1 0
0 1 1 1 1
0 0 1 1 1

3列目の2から始めて、全方向（上下左右斜め）に動けるようになりたいです。コードでは、0 が見つかるまで配列をあらゆる方向にトラバースするにはどうすればよいですか?

私の理論的な考えは、あらゆる方向に順番に反復することです。たとえば、上に行くことから始めて、2 より上の行のすべての値を確認します。

1
1
2

ゼロが見つからなかったので、右上の対角線を確認してください

   1
  1
 2

まだ0がないので、右に進みます。最初の 0 を見つけたらすぐに休憩します。

試行: 実際には、一連の if ループと for ループを使用してこれを行う方法を知っていますが、そのコードをよりシンプルで読みやすいバージョンに編集する方法を探しています。

しかし、私はJavaが初めてなので、これを行う最善の方法がわかりません。何か案は？

4

1 に答える 1

1

TwoD Iterator は明らかに良い出発点です。残りはあまり努力せずに自分でできると思います。

シナリオで最初のゼロを見つけるにはDirection、反復が終了するかゼロが見つかるまで、それぞれを反復し、その方向にボード全体を反復する必要があります。

スパイラル検索を行うには、イテレータを各方向に開始し、ステップを実行して、ゼロが見つかるポイントが返されるまで順番に各イテレータをチェックする必要があります。

public class TwoDIteratorTest {

    // An ubiquitous Point class
    static class Point {
        final int x;
        final int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "{" + x + "," + y + "}";
        }
    }

    // All possible directions.
    enum Direction {
        North(0, 1),
        NorthEast(1, 1),
        East(1, 0),
        SouthEast(1, -1),
        South(0, -1),
        SouthWest(-1, -1),
        West(-1, 0),
        NorthWest(-1, 1);
        private final int dx;
        private final int dy;

        Direction(int dx, int dy) {
            this.dx = dx;
            this.dy = dy;
        }

        // Step that way
        public Point step(Point p) {
            return new Point(p.x + dx, p.y + dy);
        }
    }

    static class TwoDIterator implements Iterable<Point> {
        // Where we are now
        Point i;
        // Direction to move in.
        private final Direction step;
        // Limits.
        private final Point min;
        private final Point max;
        // Next position to go to.
        Point next = null;

        // Normal constructor.
        public TwoDIterator(Point start, Direction step, Point min, Point max) {
            i = next = start;
            this.step = step;
            this.min = min;
            this.max = max;
        }

        // Some simplified constructors
        public TwoDIterator(int x, int y, Direction step, Point min, Point max) {
            this(new Point(x, y), step, min, max);
        }

        public TwoDIterator(int x, int y, Direction step, int minx, int miny, int maxx, int maxy) {
            this(new Point(x, y), step, new Point(minx, miny), new Point(maxx, maxy));
        }

        // The iterator.
        @Override
        public Iterator<Point> iterator() {
            return new Iterator<Point>() {
                // hasNext calculates next if necessary and checks it against the stabliched limits.
                @Override
                public boolean hasNext() {
                    if (next == null) {
                        // Step one.
                        next = step.step(i);
                        // Stop at limits.
                        if (next.x < min.x
                                || next.x > max.x
                                || next.y < min.y || next.y > max.y) {
                            next = null;
                        }
                    }
                    return next != null;
                }

                @Override
                public Point next() {
                    if (hasNext()) {
                        // Make our move.
                        i = next;
                        next = null;
                        return i;
                    }
                    return null;
                }

                @Override
                public void remove() {
                    throw new UnsupportedOperationException("Not supported.");
                }
            };
        }
    }

    public void test() {
        // Test all directions.
        for (Direction d : Direction.values()) {
            System.out.print(d + " - ");
            for (Point p : new TwoDIterator(0, 0, d, -5, -5, 5, 5)) {
                System.out.print(p + ",");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        new TwoDIteratorTest().test();
    }
}
于 2013-03-24T22:43:47.920 に答える