【算法学习笔记】76.DFS 回溯检测 SJTU OJ 1229 mine

扫雷玩得好还是有点好处的......

这个题一开始像从后向前按照第一排的数字进行DFS 发现自己真傻,先不说这种情况下每个数字的填写情况很多, 还要处理相邻位置的问题。

所以可以对每一位有没有地雷进行枚举。处理每一位的时候，要保证上一个数字是合理的，否则不用进行下去了，类似回溯，注意have变量的处理就好了。

#include <iostream>
#include <stack>
using namespace std;
//最长 暗示dfs
//遇到3 和 0 其实只有一种情况
//遇到2 和 1 有三种情况
//遇到* 有 2+2*3 = 8种情况,
//可见如果以数字为dfs的条件的话 很麻烦 还不如直接用0 1 来枚举每个炸弹的位置
//其实如果数据小的话 可以直接遍历所有可能解 然后进行验证 但是因为n过大,全部情况根本没有办法枚举完,另外就是验证的效率很低
//所以还是dfs

int n;
string nums;
bool isMine[100000+10]={false};
void init(){
    cin>>n;
    cin>>nums;
}
bool have = false;

int alreadyHave(int cur){
    int res = 0;
    res += isMine[cur];
    if(cur>0)
        res += isMine[cur-1];
    if(cur<n-1)
        res += isMine[cur+1];
    return res;
}

bool canPut(int cur){
    if(nums[cur]=='*')
        return true;
    else
        return ('0' + alreadyHave(cur) ) <= nums[cur];
}
bool exactPut(int cur){
    if(nums[cur]=='*')
        return true;
    else
        return ('0' + alreadyHave(cur) ) == nums[cur];
}

void dfs(int cur){
    if(have)
        return;
    if(cur<0){
        have = exactPut(0);
        return;
    }
    isMine[cur] = true;
    if((cur == n-1 and canPut(cur))
       or (cur<n-1 and exactPut(cur+1)) )
        dfs(cur-1);

    if(have)//不必继续
        return;

    isMine[cur] = false;
    if((cur == n-1 and canPut(cur))
       or (cur<n-1 and exactPut(cur+1)) )
        dfs(cur-1);
    return;
}


void build(){

    dfs(n-1);
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if(isMine[i])
            ans++;
    }
    cout<<ans<<endl;
    for (int i = 0; i < n; ++i)
    {
        cout<<isMine[i];
    }
    cout<<endl;
}

int main(int argc, char const *argv[])
{
    init();
    build();
    return 0;
}