程序设计大赛第三题

Question

用java或C++或C语音均可以，希望能做出来的帮我做做，我考完了现在还做不出来。谢谢谢谢
题目如下：儿童节
说明：
6.1是儿童节，AllStar09-3来到安徽师范大学附属小学开展活动，主要是给同学们做ACM竞赛的讲座（伟人说过：ACM要从娃娃抓起噢！）。他发现上课的时候总有一些同学和前后左右的人交头接耳，这是令他十分头疼的一件事情。不过，他发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的AllStar09-3想到了一个办法，或许可以减少上课时学生交头接耳的问题：他打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。 
AllStar09-3于是编写了一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。 你能做到吗？ Input 第一行：有5个用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=100，0<=K< M，0<=L< N，D< =200）。 
接下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。 
输入数据保证最优方案的唯一性。 Output 共两行。 
第一行包含K个整数，a1a2……aK，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第aK行和第aK+1行之间要开辟通道，其中ai< ai+1，每两个整数之间用空格隔开（行尾没有空格）。 
第二行包含L个整数，b1b2……bk，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第bL列和第bL+1列之间要开辟通道，其中bi< bi+1，每两个整数之间用空格隔开（行尾没有空格）。Sample Input 4 5 1 2 3 
4 2 4 3 
2 3 3 3 
2 5 2 4Sample Output 2
2 4

Answer 1

不容易啊，竟然被我整出来了，出去中间吃饭，大概花了1.5小时，参赛肯定没戏了。
实际上，这道题目的算法难度不高，但倒腾坐标够让人头疼的。我一般些代码都是比较注意代码可读性的，欢迎大家批评。算法思路：
用两个数组分别记录每一行、每一列各有多少个交头接耳者，
最后结果从这两个数组中取最大的N个即可，N取决于k，l两个参数。
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class ZuiweiGuihua { public static void main(String[] args) throws Exception{
int[] params=readParam(5,"请输入参数（M,N,K,L,D）：");
int rowCount=params[0];
int colCount=params[1];
int hSplit=params[2];
int vSplit=params[3];
int chaters=params[4];
int[] vChaterCount=new int[colCount-1];
int[] hChaterCount=new int[rowCount-1];
for(int i=0; i<chaters;){
ChatPair cp=ChatPair.parse(readParam(4,"请输入交头接耳者的坐标，共"+chaters+"个，目前是第:"+(i+1)+"个："));
if (cp!=null){
i++;
if(cp.isInOneCol()){
hChaterCount[cp.getSplitCandidate()]++;
}else if (cp.isInOneRow()){
vChaterCount[cp.getSplitCandidate()]++;
}else{
System.out.println("输入不合法，交头接耳者不在一行或者一列。");
i--;
}
}
}
System.out.println("\n计算中...\n");
System.out.print("应在如下行增加过道：");
for(int i=0; i<hSplit;i++){
int index=getMax(hChaterCount);
System.out.print(index+1+" ");
hChaterCount[index]=0;
}
System.out.print("\n应在如下列增加过道：");
for(int i=0; i<vSplit;i++){
int index=getMax(vChaterCount);
System.out.print(index+1+" ");
vChaterCount[index]=0;
}
}

private static int getMax(int[] array){
int max=array[0];
int index=0;
for(int i=0; i<array.length;i++){
if (array[i]>max){
max=array[i];
index=i;
}
}
return index;
}
private static int[] readParam(int length,String hint) throws Exception{
System.out.println(hint);
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String curLine=null;
boolean valide=false;
int[] param=new int[length];
while(!valide){
curLine=reader.readLine();
String[] segs=curLine.split(" ");
if (segs.length!=length){
segs=curLine.split(",");
}
if (segs.length!=length){
System.out.println("必须输入 " +length+ " 个数字，且以空格或者逗号分割。请重新输入：");
continue;
}else{
try {
for(int i=0; i<param.length;i++){
param[i]=Integer.parseInt(segs[i]);
if (param[i]<0){
System.out.println("必须用正整数。，请重新输入：");
break;
}
}
valide=true;
} catch (RuntimeException e) {
System.out.println("只能输入数字。请重新输入：");
continue;
}
}
}
return param;
}
}
class ChatPair{
private int x1,y1,x2,y2;
public ChatPair(){

}
public static ChatPair parse(int[] position){
if (position==null || position.length!=4){
return null;
}
ChatPair cp=new ChatPair();
cp.x1=position[0];
cp.y1=position[1];
cp.x2=position[2];
cp.y2=position[3];
return cp;
}
public boolean isInOneRow(){
return x1==x2;
}
public boolean isInOneCol(){
return y1==y2;
}
public int getSplitCandidate(){
if (isInOneRow()){
return min(y1,y2)-1;
}
if (isInOneCol()){
return min(x1,x2)-1;
}
return 0;

}

private static int min(int var1,int var2){
int min=var1;
if (var2<min){
min=var2;
}
return min;
}
}

Answer 2

楼上的程序我运行了一下：
请输入参数（M,N,K,L,D）：
3,3,3,3,3
请输入交头接耳者的坐标，共3个，目前是第:1个：
1,0.0.0.
必须输入 4 个数字，且以空格或者逗号分割。请重新输入：
2.0.0.0.
必须输入 4 个数字，且以空格或者逗号分割。请重新输入：
3,0,0,0
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at ZuiweiGuihua.main(ZuiweiGuihua.java:21)Process completed.

Answer 3

题目要求手工保证输入数据的正确性，所以就没有做太多检查，
这里很多行列的起始都是按1开始，而不是按
java数组的0开始。