[SWEA] 2112. ほごフィルム

16783 ワード
DFS brute force アルゴリズム#アルゴリズム# テキストリンク

質問へのアクセス


  • これはシミュレーション(完全探索)問題である.

  • 性能テストに合格した後、現在使用されている薬品の数が最も少ないかどうかを確認し、探索を終了する.
    そうでなければ、現在位置(d)で薬品処理を行った後、探索を継続する.
    医薬品処理を行う前に、状態を回復するために、現在の状態を保存する必要がある.(プリ配列)
    処理が終了すると、保存した値に戻ります.

  • dfs関数の因子は、現在薬品処理を行う行(d)、使用する薬品の個数(k)、保護シート情報(map)である.

  • 試験に合格した条件は、保護膜の全列(w)にK個以上の単位が連続的に存在することである.
    理解は簡単ですが、コードで実現するのはちょっと難しいです.

  • 完全探索が最後まで進むと問題は解決したが,タイムアウトが発生した.
    最小限の薬品数を求める問題であるため、k個の薬品を使用した場合にテストに合格すれば、k+1個の薬品を探索することはできない.(is_pass)
    その結果,不要な探索を行わないことで,タイムアウト問題を解決できることが分かった.

    • に答える

    #include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

int T, D, W, K, rst;
bool is_pass;
int map[14][21];

void input(){
    cin >> D >> W >> K;
    for(int i = 1; i <= D; i++){
        for(int j = 1; j <= W; j++){
            cin >> map[i][j];
        }
    }
    rst = INT_MAX;
    is_pass = false;
}

int test_pass(int map[][21]){
    for(int w = 1; w <= W; w++){
        int cnt = 1;
        bool flag = false;
        for(int d = 1; d <= D-1; d++){
            if(map[d][w] == map[d+1][w]) cnt++;
            else cnt = 1;
            if(cnt == K){ flag = true; break; }
        }
        if(!flag) return false;
    }
    return true;
}

void change(int d, int state, int map[][21]){
    for(int w = 1; w <= W; w++){
        map[d][w] = state;
    }
}

void dfs(int d, int k, int map[][21]){
    if(is_pass && k > rst) return;
    int pre[21];
    if(test_pass(map)){
        rst = min(rst, k);
        is_pass = true;
        return ;
    }
    
    for(int i = d; i <= D; i++){
        for(int w = 1; w <= W; w++) pre[w] = map[i][w]; // save
        change(i, 0, map); // A
        dfs(i + 1, k + 1, map);
        change(i, 1, map); // B
        dfs(i + 1, k + 1, map);
        for(int w = 1; w <= W; w++) map[i][w] = pre[w]; // restore
    }
}

void solve(){
    for(int i = 1; i <= D; i++){
        dfs(i, 0, map);
    }
}

int main(){
    cin >> T;
    for(int tc = 1; tc <= T; tc++){
        input();
        solve();
        cout << "#" << tc << " " << rst << endl;
    }
}
    dockerのインストール[linux/ubuntu]
    [プログラマー]フルコースを走っていない選手(Python 3)、zip()