find max path

by lizhi 06 Nov 2015

Embed

/**
 * Copyright lizhi ( http://wonderfl.net/user/lizhi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/YZwN
 */

package 
{
	import flash.display.Sprite;
	import flash.events.MouseEvent;
	import flash.text.TextField;
	/**
	 * ...
	 * @author lizhi
	 */
	public class Test extends Sprite
	{
		private var arr:Array;
		private var dir:Array = [[0,1],[0,-1],[1,0],[-1,0]];
		private var numCols:int;
		private var numRows:int;
		private var path:Array;
		private var path2:Array;
		private var paths:Array;
		private var size:int;
		private var info:TextField = new TextField;
		public function Test() 
		{
			this.x = 100;
			this.y = 100;
			
			addChild(info);
			info.autoSize = "left";
			info.y = -50;
			
			arr = [
				[1,1,1,0],
				[0,0,0,0],
				[0,0,0,1],
				[0,1,0,0]
			];
			
			numCols = arr[0].length;
			numRows = arr.length;
			
			size = 40;
			update();
			
			stage.addEventListener(MouseEvent.CLICK, stage_click);
		}
		
		private function update():void {
			path = [];
			paths = [];
			graphics.clear();
			graphics.lineStyle(3);
			for (var x:int = 0; x < numCols;x++ ) {
				for (var y:int = 0; y < numRows; y++ ) {
					if (arr[y][x]) {
						graphics.beginFill(0);
					}
					graphics.drawCircle(x * size, y * size, 10);
					graphics.endFill();
				}
			}
			
			graphics.lineStyle(0,0x999999);
			for (x = 0; x <= numCols;x++ ) {
				graphics.moveTo((x-.5) * size, -.5*size);
				graphics.lineTo((x-.5) * size, size*(numRows-.5));
			}
			for (y = 0; y <= numRows; y++ ) {
				graphics.moveTo(-.5*size,(y-.5) * size);
				graphics.lineTo( size*(numCols-.5),(y-.5) * size);
			}
			
			for (x = 0; x < numCols;x++ ) {
				for (y = 0; y < numRows; y++ ) {
					search(x,y);
				}
			}
			
			paths.sortOn("length", Array.NUMERIC|Array.DESCENDING);
			info.text = "num path:" + paths.length;
			
			graphics.lineStyle(3,0x9900);
			for (var i:int = 0; i < paths[0].length;i+=2 ){
				if(i==0)
				graphics.moveTo(paths[0][i] *size, paths[0][i+1]*size);
				else
				graphics.lineTo(paths[0][i] *size, paths[0][i+1]*size);
			}
		}
		
		private function stage_click(e:MouseEvent):void 
		{
			var x:int = Math.round(mouseX / size);
			var y:int = Math.round(mouseY / size);
			if (x >= 0 && y >= 0 && x < numCols && y < numRows) {
				arr[y][x] = 1 - arr[y][x];
				update();
			}
		}
		
		private function search(x:int, y:int):Boolean {
			if (x >= 0 && y >= 0 && x < numCols && y < numRows && arr[y][x] == 0) {
				path.push(x, y);
				arr[y][x] = 1;
				var flag:Boolean = false;
				for each(var d:Array in dir) {
					if (search(x + d[0], y + d[1])) {
						flag = true;
					}
				}
				arr[y][x] = 0;
				if (!flag) {
					paths.push(path.slice());
				}
				path.pop();
				path.pop();
				return true;
			}
			return false;
		}
	}
}