首页 > 代码库 > Uva 167 The Sultan's Successors

Uva 167 The Sultan's Successors

题目链接:Uva 167

 

思路:

    八皇后问题,采用回溯法解决问题。

代码:

 

#include <iostream>#include <string.h>using namespace std;const int MAX_N = 10;int A[MAX_N];int M[MAX_N][MAX_N];int num, Max = 0;int is_safe( int row, int col ){    for ( int i = 0; i < row; ++i )    {        if ( A[i] == col )            return false;        if ( A[i] + i == row + col )            return false;        if ( i - A[i] == row - col )            return false;    }    return true;}void dfs( int row ){    if ( row == 8 )    {        for ( int i = 0; i < 8; ++i )            num += M[i][A[i]];        if ( num > Max )            Max = num;        num = 0;        return;    }    else    {        for ( int i = 0; i < 8; ++i )        {            if ( is_safe( row , i ) )            {                A[row] = i;                dfs( row+1 );            }        }    }}int main( ){    int n;    cin >> n;    while ( n-- )    {        num = Max = 0;        memset( M, 0, sizeof( M ) );        memset( A, 0, sizeof( A ) );        for ( int i = 0; i <= 7; ++i )            for ( int j = 0; j <= 7; ++j )                cin >> M[i][j];        dfs( 0 );        printf( "%5d\n", Max );    }    return 0;}

 

Uva 167 The Sultan's Successors