PAT 1128 C++版

PAT 1128 C++版

1.题意

在编程测试中，N皇后问题是一个经典的问题。但是这次的问题不是让你找出N皇后问题的解，而是让你判断这串数字是否是针对N皇后问题的解。

2.分析

接触过N皇后问题的同学都知道，判断N皇后的解问题很简单。只需要判断所有的坐标是否成+1，-1，或者0的斜率就ok。如果满足任意两个坐标的斜率既不为1，也不为-1，也不是0的话，那么就是一个N皇后的解。

3.代码

#include<cstdio>
#define maxn 1005
int main(){
	int num,n;//num 代表的是测试用例数  n代表的是正方形的方格数
	scanf("%d",&num);
	double array[maxn];
	int i,j,k;
	double value;//判断每两个坐标间的斜率 
	int flag  = 0;
	for(i = 0;i< num;i++){
		scanf("%d",&n);
		for(j = 0;j< n;j++)
		{
			scanf("%lf",&array[j]);//将每个皇后顺序放置
		}
		
//		for(j = 0;j< n;j++){
//			printf("%f ",array[j]);
//		}
		double curValue = 0;
		for(j = 0;j< n;j++){
			flag = 0;
			curValue = array[j]; 
			//printf("curValue = %f\n",curValue);
			for(k = j+1;k< n ;k++){
				//printf("k = %d,array[k]= %d ",k,array[k]);
				value = (array[k] - array[j])/(k-j);				
				if(value == -1 || value == 1 || value == 0)	 
				{
					printf("NO\n");
					//printf("j = %d,k = %d\n",j,k);
					flag = 1; 
					break;
				}
			}			
			if(flag == 1){
				break;
			}
		//	printf("\n");
		}
		if(j == n){
			printf("YES\n");
		}
	} 
}

4.测试用例

4
8 4 6 8 2 7 1 3 5
9 4 6 7 2 8 1 9 5 3
6 1 5 2 6 4 3
5 1 3 5 2 4

1
5 1 1 1 1 1

5.执行结果

6.注意点

注意的问题有：

• 判断是否是解的点有三个：1，-1,0
• 需要注意使用double类型去解决斜率问题。而不是使用int型去保存输入额坐标值，因为要使用 这个值 去计算斜率。【如果使用int型则也会将4/3这样的值算成1】