続き
今目が覚めました。もうダメ人間の仲間入りです。いや、前からか。
azouno氏からの質問もあったので、塗りつぶしのコードを書きます。
enum MapState{ LINE, Painted, UNKNOWN }; class Map{ MapState map; int width, height; Map(int x, int y){ this.width = x; this.height = y; this.map = new MapState[x][y]; for(int i = 0; i < x; i++) for(int j = 0; j < y; j++) this.map[i][j] = MapState.UNKNOWN; } isValid(int x, int y){ return (0 <= x && x < width && 0 <= y && y < height); } public void fill(int x, int y){ if(isValid(x, y) && this.map[x][y] == MapState.UNKNOWN){ this.map[x][y] = MapState.Painted; fill(x + 1, y); fill(x - 1, y); fill(x, y + 1); fill(x, y - 1); } } }
まあ、これだと再帰が深すぎてスタックオーバーフローで落ちるわけです。もちろんアルゴリズム的には正しいんですけれど、塗りつぶす領域が大きいと落ちます。どれくらいで落ちるかについては、環境やオプションなどによると思うので分かりませんが。
こういうときには、関数コールのスタックを使わずに、ヒープ内にスタックを確保すればよいわけです。
class Map{ class Point{ int x, y; Point(int x, int y){ this.x = x; this.y = y; } } public void addStack(LinkedListstack, int x, int y){ if(isValid(x, y) && this.map[x][y] == MapState.UNKNOWN){ stack.add(new Point(x, y)); this.map[x][y] = MapState.Painted; } } public void fill(int x, int y){ LinkedList stack = new LinkedList (); if(!isValid(x, y) || this.map[x][y] != MapState.UNKNOWN) return; this.map[x][y] = Painted; stack.add(new Point(x, y)); while(!stack.isEmpty()){ Point p = stack.remove(); addStack(stack, p.x+1,p.y); addStack(stack, p.x-1,p.y); addStack(stack, p.x,p.y+1); addStack(stack, p.x,p.y-1); } } }
別に大した手法じゃないですが、一応。