UVa

UVa00167 UvaLive5277 SCU1033 The Sultan's Successors

題目連結 UVa
題目連結 UvaLive
題目連結 SCU

  • 題意：給定 $8\times 8$ 棋盤，每一格上面都有數字，要放 8 隻皇后，在彼此不衝突的情況下，每隻皇后所在位置的數字和最大為多少。
  • 題解：八皇后經典題，增加要算總和的部分。
  • 備註：hdu 1642 也是同一題，但我試都是 TLE，因此沒放上來。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    #include <iostream>
    #include <iomanip>
    using namespace std;
    #define N 100
    int vis[N][N], c[N], n;
    int a[N][N], maxx;

    void search(int cur){
    	if (cur == n){
    		int ans = 0;
    		for (int i = 0; i < n; i++)
    			ans+=a[i][c[i]];
    		maxx = (maxx>ans ? maxx : ans);
    		return;
    	}
    	else for (int i = 0; i < n; i++) {
    		if (!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]){
    			c[cur] = i;
    			vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
    			search(cur + 1);
    			vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
    		}
    	}
    	return;
    }

    int main(){
    	n = 8;
    	for (int i = 0; i < N; i++){
    		c[i] = 0;
    		for (int j = 0; j < N; j++)
    			vis[i][j] = 0;
    	}
    	int t;
    	while (cin >> t){	
    		maxx = 0;
    		for (int i = 0; i < t; i++){
    			for (int j = 0; j < n; j++)
    				for (int k = 0; k < n; k++)
    					cin >> a[j][k];
    			search(0);
    			printf("%5.d\n", maxx);
    			maxx = 0;
    		}		
    	}
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts