Swfdong's Blog

什么，有好玩的编程问题？咱可就指着这个活呐。

这次纳兰出的是一个很美好的、帮助小天约会的题目。

原帖地址：http://bbs.9ria.com/thread-62598-1-1.html

简单说来，就是有n*n的一块地图，从其中一点出发，走遍地图上所有格子，求走法，再求共有多少种走法。

当然，算法是咱弱项，不可能像flashyiyi那样不到半小时就做出来。

不过既然要做，还是带个图比较好玩一些，取长补短吧：－）

经过了n久的努力……有了下面的小程序：

源代码：

import flash.display.Shape;
import flash.events.MouseEvent;
var LENGTH:uint=4;
var GIRDSIZE:uint=160/LENGTH;
var flags:Array;
var gird:Shape=addChild(new Shape()) as Shape;
var point:Shape=addChild(new Shape()) as Shape;
var track:Shape=addChild(new Shape()) as Shape;
var result:Array;
//Draw Gird
gird.graphics.lineStyle(1,0x666666);
for (var i:uint=0; i<LENGTH+1; i+=1) {
	gird.graphics.moveTo(5+i*GIRDSIZE,50);
	gird.graphics.lineTo(5+i*GIRDSIZE,210);
	gird.graphics.moveTo(5,50+i*GIRDSIZE);
	gird.graphics.lineTo(165,50+i*GIRDSIZE);
}
//Draw Point Rect;
point.graphics.beginFill(0xDD0000);
point.graphics.drawRect(6,51,GIRDSIZE-1,GIRDSIZE-1);
point.graphics.endFill();
point.visible=false;
stage.addEventListener(MouseEvent.CLICK,clickHandler);
function clickHandler(event:MouseEvent):void {
	if (event.stageX>5&&event.stageX<165&&event.stageY>50&&event.stageY<210) {
		var x:uint=(((event.stageX-5)/GIRDSIZE)>>0),y:uint=(((event.stageY-50)/GIRDSIZE)>>0);
		point.x=x*GIRDSIZE;
		point.y=y*GIRDSIZE;
		point.visible=true;
		calc(x,y);
	}
}
function createFlags():void {
	var length:uint=LENGTH+2;
	var border:uint=LENGTH+1;
	flags=new Array(length);
	for (var i:int=0; i<length; i+=1) {
		flags[i]=new Array(length);
		for (var j:int=0; j<length; j+=1) flags[i][j]=(i==0||j==0||i==border||j==border)?false:true;
	}
}
function calc(x:uint,y:uint):void {
	x=x+1,y=y+1;
	var next:Array=[{x:x,y:y}];
	createFlags();
	result=[];
	find(next);
	output.text=LENGTH+"*"+LENGTH+"的马场，解出"+result.length+"种路线";
	//trace(LENGTH+"*"+LENGTH+"的马场，解出"+result.length+"种路线");
	drawArgs(result[(Math.random()*result.length)>>0]);
}
function find(args:Array):void {
	var currentArg:Object=args[args.length-1];
	flags[currentArg.x][currentArg.y]=false;
	var next:Array=findNext(currentArg);
	var length:uint=next.length;
	if (length>0) {
		if (args.length>=LENGTH*LENGTH-1) {
			result.push(args.concat(next[0]));
		} else {
			for (var i:uint=0; i<length; i+=1) find(args.concat(next[i]));
		}
	}
	flags[currentArg.x][currentArg.y]=true;
}
function findNext(args:Object):Array {
	var x:uint=args.x,y:uint=args.y,res:Array=[];
	if (x>0&&flags[x-1][y]) res.push({x:x-1,y:y});
	if (y>0&&flags[x][y-1]) res.push({x:x,y:y-1});
	if (x<9&&flags[x+1][y]) res.push({x:x+1,y:y});
	if (y<9&&flags[x][y+1]) res.push({x:x,y:y+1});
	return res;
}
function copyFlags(array:Array):Array {
	var length=array.length;
	var result:Array=new Array(length);
	for (var i:int=0; i<length; i+=1) result[i]=array[i].concat();
	return result;
}
function drawArgs(array:Array):void {
	var length:int=array.length;
	var xOffset:uint=5+(GIRDSIZE>>1);
	var yOffset:uint=50+(GIRDSIZE>>1);
	track.graphics.clear();
	track.graphics.lineStyle(2,(Math.random()*0xFFFFFF)>>0);
	track.graphics.moveTo(xOffset+(array[0].x-1)*GIRDSIZE,yOffset+(array[0].y-1)*GIRDSIZE);
	for (var i:int=1; i<length; i+=1) {
		track.graphics.lineTo(xOffset+(array[i].x-1)*GIRDSIZE,yOffset+(array[i].y-1)*GIRDSIZE);
	}
}

这样的算法PK活动很好，可以让大脑多转一转。

不知道下次又会PK什么题目，小天和收银MM的未来又会走向何方？

我很期待。

后记：夜深人静，有些失眠，写写代码以放松身心。

整了一个纯位运算的效率最优版本：

var LENGTH:uint=4;
var COUNTLEN:uint=LENGTH*LENGTH-1;
var GIRDSIZE:uint=160/LENGTH;
var flags:Vector.<uint>;
var count:uint=0;
calc(3,3);
function createFlags():void {
	var length:uint=LENGTH+2;
	var border:uint=LENGTH+1;
	flags=new Vector.<uint>(32,true);
	for (var i:int=0; i<length; i+=1) {
		flags[i]=0x00000000;
		for (var j:int=0; j<length; j+=1) (i==0||j==0||i==border||j==border)?(flags[i]&=~(1<<j)):(flags[i]|=1<<j);
	}
}
function calc(x:uint,y:uint):void {
	createFlags();
	count=0;
	find(x+1,y+1,0);
	trace(LENGTH+"*"+LENGTH+"的马场，解出"+count+"种路线");
}
//无记录版,和flashyiyi的算法一样...
function find(x:uint,y:uint,c:uint):void {
	if((flags[x]>>y)&1){
		flags[x]&=~(1<<y);
		if (c>=COUNTLEN) {
			count+=1;
		} else {
			c+=1;
			find(x+1,y,c);
			find(x,y+1,c);
			find(x-1,y,c);
			find(x,y-1,c);
		}
		flags[x]|=1<<y;
	}
}

不过很不幸，位运算优化的版本在我电脑上也只能跑到6*6，机器好的可以试试看：－）

Tags: AS3, 位运算, 算法