1003解法

gistfile1.js

function m(map){
	var max = 0, size = map.length;

	return proceed(0);	//回溯算法

	function proceed(pos){
		var max = 0; //放置城堡数

		for(var i = pos; i < size * size; i++){
			var y = i % size;
			var x = (i / size) | 0;
			if(canput(x, y)){
				//console.log('can put...' + i, map);
				map[x][y] = 2; //放置堡垒
				max = Math.max(max, proceed(i) + 1);
				map[x][y] = 0; //置空
			}
		}
		//console.log(max);

		return max;
	}

	function canput(x, y){
		//判断当前x、y的位置是否能放置堡垒
		if(map[x][y] !== 0){
			return false;
		}

		for(var i = x - 1; i >= 0; i--){
			if(map[i][y] == 2){
				return false;	//遇到堡垒
			}
			if(map[i][y] == 1){
				break;			//遇到墙
			}
		}

		for(var i = x + 1; i < size; i++){
			if(map[i][y] == 2){
				return false;	//遇到堡垒
			}
			if(map[i][y] == 1){
				break;			//遇到墙
			}
		}

		for(var j = y - 1; j >= 0; j--){
			if(map[x][j] == 2){
				return false;	//遇到堡垒
			}
			if(map[x][j] == 1){
				break;			//遇到墙
			}
		}

		for(var j = y + 1; j < size; j++){
			if(map[x][j] == 2){
				return false;	//遇到堡垒
			}
			if(map[x][j] == 1){
				break;			//遇到墙
			}
		}
		return true;	
	}	
}