SGU 239.Minesweeper

题意：

如图，一列未知的区域长度为n（≤1000），给出第二列的数字，求区域中雷的排列有多少种。

Solution：

　　搜索。这题看上去1000的范围很大，实际上加上合理的剪枝，状态数会变得非常非常少。

一个雷最多能影响3个格子，直接从上往下枚举这个地方有没有雷。有雷的话给影响的格子的数字减一。

出现负数，或枚举到第k个位置了，第k-2个位置的数不为0的时候都是可以退出的。

这样的搜索策略使得我们几乎不会做无用功，最多向下一层就回到了正确的方向。

实际上代码也只用了15ms

#include <iostream>

using namespace std;

int n, ans;

int s[];

void dfs ( int x )

{

    if ( x -  >  && s[x - ] !=  ) return;

    if ( x == n +  ) {

        if ( s[n] ==  ) ++ans;

        return ;

    }

    dfs ( x +  );

    int flag = ;

    for ( int i = -; i <= ; ++i ) {

        if ( ( x + i >  && x + i <= n ) && --s[x + i] <  ) flag = ;

    }

    if ( !flag ) dfs ( x +  );

    for ( int i = -; i <= ; ++i ) {

        if ( x + i >  ) ++s[x - i];

    }

}

int main()

{

    cin >> n;

    for ( int i = ; i <= n; ++i ) {

        cin >> s[i];

    }

    dfs (  );

    cout << ans << endl;

}

　　然而分析复杂度的时候我发现。。。实际上如果我们确定了第一个格子有没有雷，就可以推断出下面所有的情况！

所以只需要枚举第一个格子有没有雷就行了。显然答案的范围也在[0,2]。

　　由此可以见上面的搜索算法的时间复杂度其实也是O（n）的。

巴特西

SGU 239.Minesweeper

最新文章

热门文章