百度“变态比赛规则”算法题 java 的解法

算了,不测试了:

#include<stdio.h>
#include<conio.h>
#define NUM 8
int flags[NUM][NUM];      //这个用来记录已经摆好的棋子的影响的范围
char sets[NUM][NUM];      //这个用来记录那些位置摆了棋子

void check(int row,int col){
    int i,j;
    if(row>=NUM){//如果row>=NUM说明前8行都摆好了棋子,因此已经得到一个解
        for(i=0;i<NUM;i++){
            for(j=0;j<NUM;j++)
                printf(sets[i][j]?"*":"#");
            printf("\n");
        }
        printf("----------------------\n");
        return;
    }
    if(col>=NUM) return;    //这个说明这一行已经摆不下棋子了,无解,再往上回溯求解
    if(!flags[row][col]){   //flags[row][col]==0说明这个位置可以摆子
        i =1;
        while(i+row<NUM){   //将这个位置布子后所影响到的位置加1,注意,因为我们只需要知道对以后棋子的影响
                            //所以只对左下斜对角,列下,右下斜对角做了标记
            flags[i+row][col] ++;
            if(col+i<NUM) flags[i+row][i+col]++;
            if(col-i>=0)  flags[i+row][col-i]++;
            i++;
        }
        sets[row][col] =1;  //记录棋子位置
        check(row+1,0);     //因为这一行已经布好子,所以从下一行的开始位置开始check
        i =1;
        while(i+row<NUM){   //撤销上面做的标记
            flags[i+row][col] --;
            if(col+i<NUM) flags[i+row][i+col]--;
            if(col-i>=0)  flags[i+row][col-i]--;
            i++;
        }
        sets[row][col] =0;  //撤销棋子
    }
    check(row,col+1);       //继续试探这行的下一个位置
}
int main(){
    check(0,0);
    getch();
}

在GCC下编译通过
ps:八皇后问题就是在8*8的棋盘中每行每列各放一个皇后,并使它们互不攻击

....

网速问题，延迟的厉害，偶还以为没提交呢，，，

你的代码我看看啦，不会再到这问你啦，嘿嘿

楼上的链接打不开

解释解释了，这个代码很难懂滴

呵呵,我在原来代码上做些注释吧...
ps:在这个贴讨论与主题无关的时,楼主会不会不高兴丫

不会的。。。
反正改一下题目就可以了。。。

个人觉得注释得很清楚

以前他是没有注释的，后来加上的

自己写了段代码，只能找出一个解，以前学的动态规划都忘的差不多了，看来得找时间补补啦

import java.util.*;

public class Queen {
	private int chess[][] = new int[8][8];
	private int a[] = new int[8];
	private int b[] = new int[15];
	private int c[] = new int[15];
	private ArrayList colList = new ArrayList(); // 记录第i行皇后放置的列数
	
	// 占据位置i,j
	private void possess(int i, int j) {
		chess[i][j]=1;
		a[j]=1;
		b[i+j]=1;
		c[7+j-i]=1;
		colList.add(String.valueOf(j));
	}
	
	// 放弃
	private void giveUp(int i, int j) {
		chess[i][j]=0;
		a[j]=0;
		b[i+j]=0;
		c[7+j-i]=0;
		colList.remove(i);
	}
	
	// 判断位置i,j上是否可以被其他皇后攻击到
	private boolean isAttacked(int i, int j) {
		if(a[j]==1 || b[i+j]==1 || c[7+j-i]==1)
			return true;
		return false;
	}
	
	public void findPosition(int i, int j) {
		int col;
		if(i>7)
			return;
		if(j>7) {
			col = Integer.parseInt((String)colList.get(i-1));
			giveUp(i-1, col);
			col = Integer.parseInt((String)colList.get(i-2));
			giveUp(i-2, col);
			findPosition(i-2, col+1);
			return;
		}
		for(; j<8; j++) {
			if(!isAttacked(i, j)) {
				possess(i, j);
				findPosition(i+1, 0);
				return;
			}
		}
		col = Integer.parseInt((String)colList.get(i-1));
		giveUp(i-1, col);
		findPosition(i-1, col+1);
	}
	
	// 输出棋盘
	public void print() {
		for(int i=0; i<8; i++) {
			for(int j=0; j<8; j++)
				System.out.print(chess[i][j]+"---");
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Queen q = new Queen();
		q.findPosition(0,0);
		q.print();
	}
}

如果是公平的比賽，淘汰率不可能高於一侷比賽淘汰一個這種效率，這種效率是固定的，就是1場比賽出局一個，或者3場比賽出局一個，或者。。。。。或者。。。。（1/2*n+1，n=0 1 2 3 4...），總之就是這個意思，意思是一場比賽，出局一個，沒見過別的更高效率的公平的比賽，當然你可以給那些比較猛的加一些權重，讓他們本身就有更高的優勢，既然你需要更高的淘汰率，那麽就直接來一個不公平的比賽嘍，隨便怎麽設定，根據個人喜好，你加多少料就加多少料，自助餐一樣哦，所以你可先排出一個1 2 3 4。。。來，然後先問前後兩個是否認可，認可就直接淘汰，不認可就打一侷，很簡單哦，很高效哦，很適合你們baidu的風格，這樣的效率zai 0.5--1之間，這麽牛的公司的這麽牛的問題，只適合這麽牛的回答，I think