回朔法

(選擇 跳下一步 清空)

回朔法

/*
 * AP325
 * Q-1-10. 最多得分的皇后
*/
#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n;
int cnt = 0;
int max_sum = 0;

int solve(int row,int col,vector<vector<int>> &board,vector<vector<int>> &score){
	if(row>=n){    
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				cout << board[i][j] << " ";
			    if(board[i][j]){
			    	sum+=score[i][j];
			    }
			}
			cout << "\n";
		}
		cout << "\n";
		max_sum = (max_sum>sum) ? max_sum : sum;
		return 0;
	}
	for (int col = 0; col < n; col++) { //試橫的
		bool isOk = true;
		// 檢查|直的
		for (int i = 0; i < row; ++i) {
		    if (board[i][col] == 1) {
		        isOk=false;
		    }
		}
		// 檢查\主對角線
		for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
		    if (board[i][j] == 1) {
		            isOk=false;
		    }
		}
		// 檢查/副對角線
		for (int i = row, j = col; i >= 0 && j < n; --i, ++j) {
		    if (board[i][j] == 1) {
		        isOk=false;
		    }
		}
		//
		int isPut = false;
		if(isOk){ //可以放為1 往下走
			isPut = true;
            board[row][col] = 1; 
            solve(row+1,col, board,score);
            board[row][col] = 0;
        }
        if(col==n-1 && isPut==false){
        	solve(row+1,0, board,score);
        }
	}
	return 0;
}
int main(){
    cin >> n;
    vector<vector<int>>board(n, vector<int>(n, 0));
    vector<vector<int>>score(n, vector<int>(n, 0));
    for(int i=0;i<n;i++){
    	for(int j=0;j<n;j++){
    		cin >> score[i][j];
    	}
    }
    solve(0,0,board,score);
    cout << "all: " << cnt << endl;
    cout << "max score: " << max_sum << endl;
}