道順を数える
via http://ja.doukaku.org/221/
左上の点から右下の点までいくのに何通りの経路があるかを数えて、左上に表示します。
定数になっている、X_COUNT と Y_COUNT の値を変更すると経路の数が変更できます。
経路上の線をクリックすると、通行止めにできます。その時経路の数も変更されます。
/**
* Copyright Horiuchi_H ( http://wonderfl.net/user/Horiuchi_H )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/kGZE
*/
package
{
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
[SWF(width=465, height=465, frameRate=30, backgroundColor="#ffffff")]
/**
* via http://ja.doukaku.org/221/
* 左上の点から右下の点までいくのに何通りの経路があるかを数えて、左上に表示します。
* 定数になっている、X_COUNT と Y_COUNT の値を変更すると経路の数が変更できます。
* 経路上の線をクリックすると、通行止めにできます。その時経路の数も変更されます。
*/
public class CountPath extends Sprite
{
public static const X_COUNT:int = 3;
public static const Y_COUNT:int = 4;
public static const OFFSET:Point = new Point(30, 30);
private var answer:TextField = new TextField();
private var nodeMap:Array = new Array();
public function CountPath() {
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e:Event = null):void {
removeEventListener(Event.ADDED_TO_STAGE, init);
var maxCount:int = (X_COUNT > Y_COUNT)? X_COUNT: Y_COUNT;
var scale:Number = 400.0 / maxCount;
var offset:Point = new Point(OFFSET.x, OFFSET.y);
offset.x += Number(maxCount - X_COUNT) * scale / 2;
offset.y += Number(maxCount - Y_COUNT) * scale / 2;
for (var y:int = 0; y <= Y_COUNT; y++) {
nodeMap[y] = new Array();
for (var x:int = 0; x <= X_COUNT; x++) {
var node:Node = new Node(x, y);
node.draw(this.graphics, scale, offset);
nodeMap[y][x] = node;
if (y > 0) {
var yEdge:Edge = new Edge(nodeMap[y - 1][x], nodeMap[y][x]);
yEdge.draw(scale, offset);
addChild(yEdge);
}
if (x > 0) {
var xEdge:Edge = new Edge(nodeMap[y][x - 1], nodeMap[y][x]);
xEdge.draw(scale, offset);
addChild(xEdge);
}
}
}
answer.autoSize = TextFieldAutoSize.LEFT;
answer.x = 10;
answer.y = 1;
addChild(answer);
displayCount();
this.addEventListener(MouseEvent.CLICK, function(event:MouseEvent):void {
displayCount();
});
}
public function displayCount():void {
answer.text = String(calcRouteCount());
}
public function calcRouteCount():int {
clearCount();
var startNode:Node = nodeMap[0][0];
var endNode:Node = nodeMap[Y_COUNT][X_COUNT];
startNode.nodeCount = 1;
calcCount(startNode);
return endNode.nodeCount;
}
private function calcCount(start:Node):void {
for each(var edge:Edge in start.getEdges()) {
if (edge.passable) {
var node:Node = edge.end;
node.nodeCount += start.nodeCount;
calcCount(node);
}
}
}
private function clearCount():void {
for each(var array:Array in nodeMap) {
for each (var node:Node in array) {
node.nodeCount = 0;
}
}
}
}
}
import flash.display.Graphics;
import flash.display.Sprite
import flash.events.MouseEvent;
import flash.geom.Point;
class Node {
private var x_:int;
private var y_:int;
private var edges:Vector.<Edge> = new Vector.<Edge>();
private var count:int = 0;
public function Node(x:int, y:int) {
this.x_ = x;
this.y_ = y;
}
public function get X():int { return this.x_; }
public function get Y():int { return this.y_; }
public function getViewX(scale:Number, offset:Point):Number {
return this.X * scale + offset.x;
}
public function getViewY(scale:Number, offset:Point):Number {
return this.Y * scale + offset.y;
}
public function get nodeCount():int { return count; }
public function set nodeCount(count:int):void { this.count = count; }
public function getEdges():Vector.<Edge> {
return edges;
}
public function addEdge(e:Edge):void {
edges.push(e);
}
public function draw(g:Graphics, scale:Number, offset:Point):void {
g.lineStyle();
g.beginFill(0x000000, 0.9);
g.drawCircle(getViewX(scale, offset), getViewY(scale, offset), 10);
g.endFill();
}
}
class Edge extends Sprite {
private var startNode:Node;
private var endNode:Node;
private var pass:Boolean = true;
public function Edge(start:Node, end:Node) {
this.startNode = start;
this.endNode = end;
this.addEventListener(MouseEvent.CLICK, function(event:MouseEvent):void {
alpha = 1.0 - alpha;
pass = !pass;
});
this.startNode.addEdge(this);
}
public function get start():Node { return this.startNode; }
public function get end():Node { return this.endNode; }
public function get passable():Boolean { return this.pass; }
public function draw(scale:Number, offset:Point):void {
var g:Graphics = this.graphics;
g.lineStyle(5, 0x000000, 0.8);
g.moveTo(startNode.getViewX(scale, offset), startNode.getViewY(scale, offset));
g.lineTo(endNode.getViewX(scale, offset), endNode.getViewY(scale, offset));
this.alpha = 0.8;
}
}