首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。