学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2822

function dogs() {
		var data = getData();
		var s = data.start;
		var t = data.target;
		var w = data.w;
		var h = data.h;

		var open = [];
		var close = [];

		var rst = cal(data);

		$('body').append(disp(rst));

		function cal(data) {

			s.h = H(s);
			s.p = null;// 父节点,即上一步
			open.push(s);

			var count = 2000;
			while (open.length != 0 && count-- > 0) {
				var cur = open.shift();
				close.push(cur);
				if (cur.x == t.x && cur.y == t.y) {
					return cur;
				}
				var arr = [ {
					x : cur.x - 1,
					y : cur.y
				}, {
					x : cur.x + 1,
					y : cur.y
				}, {
					x : cur.x,
					y : cur.y - 1
				}, {
					x : cur.x,
					y : cur.y + 1
				} ];

				for ( var i = 0; i < arr.length; i++) {
					var ai = arr[i];
					if (check(ai)) {
						ai.h = H(ai) + cur.h;
						ai.p = cur;
						// 插入
						var j = 0;
						for (; j < open.length; j++) {
							var oi = open[j];
							if (ai.h < oi.h) {
								break;
							}
						}
						open.splice(j, 0, ai);
					}
				}

			}

		}

		// 检测是否可以放入open
		function check(myPoint) {
			var rst = true;
			if (myPoint.x == -1 || myPoint.y == -1 || myPoint.x == h
					|| myPoint.y == w) {
				rst = false;
			}
			for ( var i = 0; i < close.length && rst; i++) {
				var ci = close[i];
				if (ci.x == myPoint.x && ci.y == myPoint.y) {
					rst = false;
					break;
				}
			}
			for ( var i = 0; i < open.length && rst; i++) {
				var oi = open[i];
				if (oi.x == myPoint.x && oi.y == myPoint.y) {
					rst = false;
					break;
				}
			}
			return rst;
		}

		// 估价函数
		function H(myPoint) {
			var rst = 0;
			var dig = 0;
			if (data[myPoint.x][myPoint.y] == 0) {
				dig = 10000;
			}
			rst = Math.abs(myPoint.x - t.x) + Math.abs(myPoint.y - t.y) + dig;
			return rst;
		}

		function disp(endPoint) {
			var rst = [];
			while (endPoint) {
				if (data[endPoint.x][endPoint.y] == 0) {
					rst.push((endPoint.x + 1) + "," + (endPoint.y + 1));
				}
				endPoint = endPoint.p;
			}
			rst = "<br/>" + rst.reverse().join('<br/>');
			return rst;
		}

		function getData() {
			var rst = [];
			rst.push('001000'.split(''));
			rst.push('111010'.split(''));
			rst.push('000010'.split(''));
			rst.push('100000'.split(''));
			rst.push('100000'.split(''));
			rst.push('101000'.split(''));
			rst.start = {
				x : 2,
				y : 4
			};
			rst.target = {
				x : 5,
				y : 2
			};
			rst.h = rst.length;
			rst.w = rst[0].length;
			return rst;
		}
	}