程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 11214

11214

編輯:關於C++

IDA*算法, 從小到大枚舉深度上限,不過該題是有深度上限的,題目中的第一個樣例表明:最多需要5個皇後就可以覆蓋整個棋盤 。

利用紫書上的技巧,我們可以快速的判斷任意兩個棋子是不是在同一行、同一列、同一對角線 (詳情見紫書P193那兩個圖)。

這樣之後暴力搜索就可以了 。 每一層需要O(nm)的復雜度,但是實際上並不需要那麼大的復雜度 。和八皇後問題類似 , 當前行之前的行已經放置了皇後,所以不必在管,每次從下一行開始放置就好 。

細節見代碼:

#include
using namespace std;
int n,m,maxd,kase = 0,vis[10][30];
char s[15][15];
bool dfs(int cur,int r) {
    if(cur == maxd) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++)
                if(s[i][j] == 'X' && !vis[0][i] && !vis[1][j] && !vis[2][i+j] && !vis[3][i-j+11]) return false;
        }
        return true;
    }
    for(int i=r;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(!vis[0][i] || !vis[1][j] ||!vis[2][i+j] ||!vis[3][i-j+11]) {
                int v1 = vis[0][i], v2 = vis[1][j], v3 = vis[2][i+j], v4 = vis[3][i-j+11];//注意,一定要恢復“原樣”
                vis[0][i] = vis[1][j] = vis[2][i+j] = vis[3][i-j+11] = 1;
                if(dfs(cur+1,i+1)) return true;
                vis[0][i] = v1; vis[1][j] = v2; vis[2][i+j] = v3; vis[3][i-j+11] = v4;
            }
        }
    }
    return false;
}
int main() {
    while(~scanf(%d,&n)&&n) {
        scanf(%d,&m);
        for(int i=1;i<=n;i++) scanf(%s,s[i]+1);
        for(maxd = 1; maxd < 5 ; ++maxd) {
            memset(vis,0,sizeof(vis));
            if(dfs(0,0)) break;
        }
        printf(Case %d: %d
,++kase,maxd);
    }
    return 0;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved