游客 注册 | 登录
中文 | En

3966 - E. n皇后摆放问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。在n×n格的棋盘上，已经摆放好其它的一些棋子，皇后与皇后之间如果有棋子，就不能相互攻击，求出在n×n的棋盘上可以摆放最多的相互不能攻击的皇后数。

题目输入

首先输入n（n<=4），然后输入n×n的棋盘，”X”表示已经摆放了的棋子，”.”表示棋盘空位。

题目输出

输出最多能摆放的皇后数。

输入/输出样例

输入格式

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....

输出格式

4
1
2
2
4

C++解答

//回溯法
#include<iostream>
#include<string>
using namespace std;
char map[4][4];
int best, n;
int place(int row, int col)
{
	int i;
	for (i = col - 1; i >= 0; i--){   //向左方向
		if (map[row][i] == 'X') break;
		if (map[row][i] == '1') return 0;
	}
	int j = col;
	for (i = row - 1; i >= 0; i--){   //左上方向
		j--;
		if (j<0) break;
		if (map[i][j] == 'X') break;
		if (map[i][j] == '1') return 0;
	}
	j = col;
	for (i = row - 1; i >= 0; i--){   //右上方向
		j++;
		if (j>n - 1) break;
		if (map[i][j] == 'X') break;
		if (map[i][j] == '1') return 0;
	}

	for (i = row - 1; i >= 0; i--){  //向上方向
		if (map[i][col] == 'X') break;
		if (map[i][col] == '1') return 0;
	}

	return 1;
}
void Backtrack(int t, int sum)
{
	if (t >= n*n){
		if (sum>best) best = sum;
		return;
	}
	int col, row;
	row = t / n; col = t%n;
	if (map[row][col] == '.'){
		if (place(row, col))
		{

			map[row][col] = '1'; //放炮后，递归
			Backtrack(t + 1, sum + 1);
			map[row][col] = '.';//不放炮，递归
		}
	}
	Backtrack(t + 1, sum);
}

int main()
{
	while (cin >> n)
	{
		int i;
		int j;
		for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			cin >> map[i][j];
		best = 0;
		Backtrack(0, 0);
		cout << best << endl;
	}
	return 0;
}

Java解答



import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner input = new Scanner(new BufferedInputStream(System.in));
		while(input.hasNext()){
			int n = Integer.parseInt(input.nextLine());
			char[][] chessboardArr = new char[n][n];
			for(int i = 0;i < n;i++){
				String str = input.nextLine();
				for(int j = 0;j < n;j++){
					chessboardArr[i][j] = str.charAt(j);
				}
			}
			int[] max = new int[2];
			for(int i = 0;i < chessboardArr.length;i++)
				for(int j = 0;j < chessboardArr.length;j++)
					findMax(chessboardArr,i,j,max);
			System.out.println(max[0]);
		}
	}

	private static void findMax(char[][] chessboardArr,int x,int y,int[] max) {
		if(y >= chessboardArr.length){
			x++;
			y = 0;
		}
		if(x >= chessboardArr.length){
			if(max[1] > max[0])
				max[0] = max[1];
			max[1] = 0;
			return;
		}
		if(canPlace(chessboardArr,x,y)){
			chessboardArr[x][y] = 'Q';
			max[1]++;
			findMax(chessboardArr,x,y + 1,max);
			chessboardArr[x][y] = '.';
		}else{
			findMax(chessboardArr,x,y + 1,max);
		}
	}

	private static boolean canPlace(char[][] chessboardArr, int x, int y) {
		boolean canPlace = true;
		if(chessboardArr[x][y] == 'X')
			canPlace = false;
		if(canPlace)
			for(int i = x;i >= 0;i--){
				if(chessboardArr[i][y] == 'X')
					break;
				if(chessboardArr[i][y] == 'Q'){
					canPlace = false;
					break;
				}
			}
		
		if(canPlace)
			for(int i = y;i >= 0;i--){
				if(chessboardArr[x][i] == 'X')
					break;
				if(chessboardArr[x][i] == 'Q'){
					canPlace = false;
					break;
				}
			}
		
		if(canPlace)
			for(int i = x,j = y;i >= 0 && j >= 0;i--,j--){
				if(chessboardArr[i][j] == 'X')
					break;
				if(chessboardArr[i][j] == 'Q'){
					canPlace = false;
					break;
				}
			}
		
		if(canPlace)
			for(int i = x,j = y;i >= 0 && j < chessboardArr.length;i--,j++){
				if(chessboardArr[i][j] == 'X')
					break;
				if(chessboardArr[i][j] == 'Q'){
					canPlace = false;
					break;
				}
			}
		
		return canPlace;
	}
}
请先登陆