DLX

Dancing Link X 求精确覆盖与重复覆盖入门

Posted on

DLX算法入门文……主要说一下我对这个算法的理解。

问题描述

精确覆盖问题:

以矩阵模型介绍,给你一个矩阵,其每个格子的权值范围是 [0,1] ,让你选出若干行,使得选出的行的 1 覆盖了一行的所有格子,且不能有重叠。

重复覆盖问题:

与精确覆盖问题基本相同,但是所选的行集合中,同一列的 1 允许重叠。
这个问题当然不可能让你输出可行方案,输出的应该是行数最小的方案。

算法理解

精确覆盖和重复覆盖都是NP问题,通常的,我们只能通过搜索去解决它。事实上DLX算法也是基于搜索算法。这里放上我的学习博客,里面讲的非常详细,一般人写的博客已然不会超过他。
所以我写这个个人理解其实主要是给自己看的。

首先最容易的当然是 \( 2^{row} \) 的最简单的裸搜,这谁都想得到……而且复杂度很高……

其实当我们选中一行时,对于这一行的每一个 1 元素,含有与选中行同一列的 1 元素的行自然是不能选的,与此同时对于选中行每一个 1 元素,它所在的列其实我们也已经不再需要去考虑它们,因此,我们可以把这些元素删除,得到一个新的矩阵,如此重复操作,直到能覆盖一行的所有格子。

基本的原理就是这些,因为涉及到非常多的增删数据,使用链表是非常非常高效且合理的!!
因为给定的图一般是稀疏图,所以如果只记录 1 的位置将会非常省内存。

而对于重复覆盖,与精确覆盖基本一致,因为找最小的原因,还可以加一个 A * 优化。

入门实践与模板

HihoCoder 1317 搜索四·跳舞链

题意:
最基本的精确覆盖入门题

思路:
模板题……

而且非常意外的发现网上的模板相似度非常高!!
所以我这里也就改了一蛤变量名就没了。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string.h>
#include <string>
#include <utility>
#include <vector>

#define ll long long

using namespace std;

const int maxnode = 1e5 + 10;
const int maxm = 1e3 + 5;
const int maxn = 1e3 + 5;

struct DLX {
    int n, m, size;
    int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; //L,R,D,U四个数组记录某节点上下左右邻居
    int head[maxn], ccnt[maxm];                                                     //head记录排头,ccnt记录某列有多少个节点
    int ansd, ans[maxn];
    void init(int _n, int _m)
    {
        n = _n;
        m = _m;
        for (int i = 0; i <= m; i++) {
            ccnt[i] = 0;
            U[i] = D[i] = i;
            L[i] = i - 1;
            R[i] = i + 1;
        }
        R[m] = 0;
        L[0] = m;
        size = m;
        for (int i = 1; i <= n; i++)
            head[i] = -1;
    }

    void link(int r, int c)
    {
        ++ccnt[Col[++size] = c];
        Row[size] = r;
        D[size] = D[c];
        U[D[c]] = size;
        U[size] = c;
        D[c] = size;
        if (head[r] < 0)
            head[r] = L[size] = R[size] = size;
        else {
            R[size] = R[head[r]];
            L[R[head[r]]] = size;
            L[size] = head[r];
            R[head[r]] = size;
        }
    }

    void exactRemove(int c)
    {
        L[R[c]] = L[c];
        R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                --ccnt[Col[j]];
            }
    }

    void repeatRemove(int c)
    {
        for (int i = D[c]; i != c; i = D[i])
            L[R[i]] = L[i], R[L[i]] = R[i];
    }

    void repeatResume(int c)
    {
        for (int i = U[c]; i != c; i = U[i])
            L[R[i]] = R[L[i]] = i;
    }

    int f()
    {
        bool vv[maxm];
        int ret = 0, c, i, j;
        for (c = R[0]; c != 0; c = R[c])
            vv[c] = 1;
        for (c = R[0]; c != 0; c = R[c])
            if (vv[c]) {
                ++ret, vv[c] = 0;
                for (i = D[c]; i != c; i = D[i])
                    for (j = R[i]; j != i; j = R[j])
                        vv[Col[j]] = 0;
            }
        return ret;
    }

    void repeatDance(int d)
    {
        if (d + f() >= ansd)
            return; //估价函数剪枝,A*搜索
        if (R[0] == 0) {
            if (d < ansd)
                ansd = d;
            return;
        }
        int c = R[0], i, j;
        for (i = R[0]; i; i = R[i])
            if (ccnt[i] < ccnt[c])
                c = i;
        for (i = D[c]; i != c; i = D[i]) {
            repeatRemove(i);
            for (j = R[i]; j != i; j = R[j])
                repeatRemove(j);
            repeatDance(d + 1);
            for (j = L[i]; j != i; j = L[j])
                repeatResume(j);
            repeatResume(i);
        }
    }

    void exactResume(int c)
    {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
                ++ccnt[Col[U[D[j]] = D[U[j]] = j]];
        L[R[c]] = R[L[c]] = c;
    }

    //d为递归深度
    bool exactDance(int d)
    {
        if (R[0] == 0) {
            ansd = d;
            return true;
        }
        int c = R[0];
        for (int i = R[0]; i != 0; i = R[i])
            if (ccnt[i] < ccnt[c])
                c = i;
        exactRemove(c);
        for (int i = D[c]; i != c; i = D[i]) {
            ans[d] = Row[i];
            for (int j = R[i]; j != i; j = R[j])
                exactRemove(Col[j]);
            if (exactDance(d + 1))
                return true;
            for (int j = L[i]; j != i; j = L[j])
                exactResume(Col[j]);
        }
        exactResume(c);
        return false;
    }

    void output()
    {
        printf("%d", ansd);
        for (int i = 0; i < ansd; i++)
            printf(" %d", ans[i]);
        puts("");
    }
};

DLX dlx;
int main()
{
    int n, m, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        dlx.init(n, m);
        for (int i = 1, num; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%d", &num);
                if (num == 1)
                    dlx.link(i, j);
            }
        if (!dlx.exactDance(0))
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}
同余BFS

HDU 6071 Lazy Running

Posted on

第一次刷到HDU第一名,趁现在没人比我高,截图来一发!!!!

对于这道题,我只想说一个字

妙!!!!

题意:
给你四个点,(1,2),(2,3),(3,4),(4,1)之间都有一条无向路径,让你从 2 号点出发,最后回到2号点,同时使得走过的距离大于等于 k ,并且 最小。

k很大,最大达到 1e18 ,四条路的范围不大于 3e4 。

思路:
这道题真的是太妙了!!!

说一下我比赛前后的思路,这里我称 从 起点 2 回到 2的回路为 E 回路。

先说一下我比赛的思路:
一开始我的思路是这样的,首先不考虑单纯的往返,那么E回路就有7种情况。
那么我考虑复杂度的话最多的就是4点成环且只有4条边的情况,对于这条已有的E回路,我们可以在任意一条路径走来回走,使得路径长度增大。
那么我们就可以将问题转化成为 \( a_1 \times x + a_2 \times y + a_3 \times z + a_4 \times p \geq k \) 这样的不等式 4点4边成环需要特殊判断
四个系数为 [0,1e18] ,我们要求找到四个系数,使得不等式成立并且左边的值最小。
可以考虑用 二分 做。但是明显复杂度不够而且很难实现……

*正解 : *

同余 bfs (以前被我叫作 数位bfs……)

首先对于一个已得的E回路,我们可以用任一一条E回路对它进行扩展。
因为这个图的E回路有无穷多个,我这里任取一条 为 a 。

假设已得E回路 p ,有E回路 a , 那么必然存在一条拓展E回路 p + a。
同理,必然存在\( p + n \times a \) 的拓展E回路。
那么对于 \( p + n \times a \geq k \) ,那么 我们只要找出最小的 满足条件 的 p 。而这里的条件就是 \( p \in \left[ 0 , a \right) \)。

答案开始显然了起来
对于一个E回路 eu ,我么只要找到 最小的 p 使得 \( p + n \times eu \geq k \) 即可。
其中 \( p \in \left[ k \% eu , eu\right) \)
那么,eu 的范围将影响到我们整个算法的复杂度,所以我们应取 eu 为 最小,而最小的 E回路为
\( \min \left( d_{2,1} , d_{2,3} \right) \times 2 \)

有个需要注意的地方就是我们在取同余距离的时候要注意不能超过原本的 k ,这里只要限制一下就可以了。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int maxn = 6e4 + 10;

ll k, times;
int d[5], w, ans;
bool vis[4][maxn];

struct node {
    int pos, val;
    ll time;
    node() {}
    node(int p, int v, ll t) { pos = p, val = v, time = t; }
};

queue<node> que;

void bfs(int st)
{
    fill(vis, false), vis[st][0] = true;
    node cur;
    int tmp, l, r;
    que.push(node(st, 0, 0));
    while (!que.empty()) {
        cur = que.front();
        que.pop();
        if (cur.pos == st && cur.val >= k)
            ans = min(ans, cur.val);
        l = (cur.pos + 3) & 3, r = (cur.pos + 1) & 3;
        if (!vis[l][(tmp = cur.val + d[l]) % w] && tmp / w + cur.time <= times) {
            que.push(node(l, tmp % w, tmp / w + cur.time));
            vis[l][tmp%w] = true;
        }
        if (!vis[r][(tmp = cur.val + d[cur.pos]) % w] && tmp / w + cur.time <= times) {
            que.push(node(r, tmp % w, tmp / w + cur.time));
            vis[r][tmp%w] = true;
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld", &k);
        each(i, 4) scanf("%d", d + i);
        w = 2 * min(d[0], d[1]), times = k / w, k %= w, ans = inf;
        bfs(1);
        if (ans < inf)
            printf("%lld\n", w * times + ans);
        else
            printf("%lld\n", (times + 1) * w);
    }
    return 0;
}
BFS

CodeForces 295C Greg and Friends

Posted on

bfs + dp 好题。
真好,比赛的时候想不出来,看题解的时候感觉好复杂……
看完写的时候感觉非常流畅!

题意:
载人过岸,一艘船最大载重 k 已经给定。每个人的重量只会是50或者100。问最小的过岸次数与方案数。

思路:
老实说这个题目我可以看就知道是道搜索题,因为和那个什么东西(就是搜索入门的那个)来着非常像。
最重要的还是理清状态与思路。
以左岸50重人数,100重人数,船是否在左岸表示一个状态,对他进行 bfs ,只要满足船重量大于 0 并且小于等于最大 k,每次过岸花费 1 。第一个搜索到 最终状态的就是我们要求的结果。

而我们的方案数,只能通过dp来球,dp最讲求的就是状态,

转移方程如下:

如果是 左岸 -- > 右岸 anum表示 50重总人数 , bnum 表示 100重 总人数

\( dp[x][y][0] += dp[a][b][1] \times C_a^{a-x} \times C_b^{b-y} \)

否则

\( dp[x][y][1] += dp[a][b][0] \times C_{anum-a}^{x-a} \times C_{bnum-b}^{y-b} \)

写到中间的时候突然发现组合数求不来……尴尬……百度了一下,在数据较小的时候可以直接递推求

\( C_n^m = C_n^{m-1} + C_{n-1}^{m-1} \)

AC Code

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn = 55;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

int n, k;
int anum, bnum, maxa, maxb;
ll dp[maxn][maxn][2], c[maxn][maxn], dis[maxn][maxn][2];

struct status {
    int an;
    int bn;
    int isLeft;
    status() {}
    status(int _an, int _bn, int _isLeft)
        : an(_an)
        , bn(_bn)
        , isLeft(_isLeft)
    {
    }
};

queue<status> que;

int bfs()
{
    c[0][0] = 1;
    for (int i = 1; i <= 50; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    maxa = anum > 0 ? k / anum : 0, maxb = bnum > 0 ? k / bnum : 0;
    que.push(status(anum, bnum, 1));
    dis[anum][bnum][1] = 0;
    dp[anum][bnum][1] = 1;
    status now, nxt;
    while (!que.empty()) {
        now = que.front();
        que.pop();
        if (!now.an && !now.bn && !now.isLeft)
            return dis[0][0][0];
        for (int i = 0; i <= maxb; i++)
            for (int j = i ? 0 : 1; j <= maxa; j++) {
                if (i * 100 + j * 50 > k)
                    break;
                if (now.isLeft) {
                    if (now.an - j < 0 || now.bn - i < 0)
                        continue;
                    nxt.an = now.an - j, nxt.bn = now.bn - i, nxt.isLeft = false;
                    (dp[nxt.an][nxt.bn][0] += dp[now.an][now.bn][1] * c[now.an][j] % mod * c[now.bn][i] % mod) %= mod;
                    if (!dis[nxt.an][nxt.bn][0]) {
                        dis[nxt.an][nxt.bn][0] = dis[now.an][now.bn][1] + 1;
                        que.push(nxt);
                    }
                } else {
                    if (now.an + j > anum || now.bn + i > bnum)
                        continue;
                    nxt.an = now.an + j, nxt.bn = now.bn + i, nxt.isLeft = true;
                    (dp[nxt.an][nxt.bn][1] += dp[now.an][now.bn][0] * c[anum - now.an][j] % mod * c[bnum - now.bn][i] % mod) %= mod;
                    if (!dis[nxt.an][nxt.bn][1]) {
                        dis[nxt.an][nxt.bn][1] = dis[now.an][now.bn][0] + 1;
                        que.push(nxt);
                    }
                }
            }
    }
    return -1;
}

int main()
{
    int weight;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight);
        if (weight == 50)
            anum++;
        else
            bnum++;
    }
    int step = bfs();
    if (step == -1) {
        puts("-1\n0");
    } else
        printf("%d\n%lld\n", step, dp[0][0][0]);
    return 0;
}

DFS

HDU 4405 Aeroplane chess

Posted on

昨天周赛的水搜索 然而………………

因为昨晚基地灯坏了,只能跟寝室里的煞笔一起打(当然他比我强,他10分钟A了 我越写越急

最后写了两个小时………………

不想多说什么了 先贴上源代码 再分析优化

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
char str[20];
int flag[20];
int len, ans;

bool judge()
{
    int mid;
    for (mid = 0; mid < len; mid++)
        if (flag[mid] == 2)
            break;
    if (mid == len)
        return false;
    long long lans = str[0] - '0', rans = str[mid] - '0', i;
    for (i = 1; i < mid; i++)
        if (flag[i])
            break;
        else
            lans = lans * 10 + str[i] - '0';
    while (i < mid) {
        long long tmp = str[i] - '0';
        i++;
        while (flag[i] == 0) {
            tmp = tmp * 10 + str[i] - '0';
            i++;
        }
        lans += tmp;
    }
    for (i = mid + 1; i < len; i++)
        if (flag[i])
            break;
        else
            rans = rans * 10 + str[i] - '0';
    while (i < len) {
        long long tmp = str[i] - '0';
        i++;
        while (flag[i] == 0) {
            tmp = tmp * 10 + str[i] - '0';
            i++;
        }
        rans += tmp;
    }
    return lans == rans;
}

void dfs(int pos, bool has_equal)
{
    if (pos == len) {
        if (has_equal && judge())
            ans++;
        return;
    }
    if (has_equal) {
        flag[pos] = 1;
        dfs(pos + 1, true);
        flag[pos] = 0;
        dfs(pos + 1, true);
    } else {
        flag[pos] = 0;
        dfs(pos + 1, false);
        flag[pos] = 1;
        dfs(pos + 1, false);
        // if(pos==len-1) return;
        flag[pos] = 2;
        dfs(pos + 1, true);
    }
}

int main()
{
    while (scanf("%s", str) != EOF) {
        if (strcmp(str, "END") == 0)
            break;
        len = strlen(str), ans = 0;
        memset(flag, 0, sizeof flag);
        flag[len] = 1000;
        dfs(1, false);
        printf("%d\n", ans);
    }
    return 0;
}

我当时的思路很明显了 先用DFS放置所有 + = 的位置 到最后判断一些能不能使等式成立

因为前面想的少,搞得后面的bug处理特别多

尤其是判断那里

对于优化建议

1.完全可以预处理一下 比如定义一个二维数组 num[27][27] 用num[x][y]表示 x-y 的数字 然后只要判断加号位置就好了

2.另外的话可以以一个循环判断=的位置 再对左右按序DFS 即可

好吧 我已经理论优化了

最后想说的是 打ACM 心态很重要 心态爆炸了 这场基本也是完了

BFS

HDU 1664 Different Digits

Posted on

稍微有点不一样 这次衡量的第一标准是位数的多少 第二标准才是数的大小
这里必须有一个 数论的 知识 不然不好写(I hate number theroy ......
对于任意的整数n,必然存在一个由不多于两个的数来组成的一个倍数。(之前写过数位BFS的应该可以理解
因为a,aa,aaa……取n+1个,则必有两个模n余数相同,相减即得n的倍数m。而m只由a、0组成。(这可以说是最糟的情况
所以只要先枚举所有的 1-9 的数 如果不存在 再枚举两个数的情况 (一直很奇怪网上的题解 0-9 不是有 45种情况么…………

还有 。。。沃特么也是SB 被自己坑到了 我还以为必须是他给的数 的位数作为范围 因为样例就是这样的…… 结果WA了好几发

AC Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>

using namespace std;
const int maxn=65540;
const int inf=0x3f3f3f3f;
int n,k,num[11],a[5];
char ch[3];
bool vis[maxn],flag[11];
string curans,ans;

struct node
{
    char ch;
    int pre,mod;
}que[maxn*10];

void getstr(int x)
{
    if(que[x].pre!=-1)
        getstr(que[x].pre);
    curans+=que[x].ch;
}

bool bfs(int kk)
{
    memset(vis,false,sizeof vis);
    int l=1,r=1;
    for(int i=0;i<kk;i++) if(a[i])
    {
        que[r].pre=-1;
        vis[que[r].mod=a[i]%n]=true;
        que[r].ch=a[i]+'0';
        r++;
    }
    while(l<r)
    {
        for(int i=0;i<kk;i++)
        {
            int tmp=que[r].mod=(que[l].mod*10+a[i])%n;
            if(!vis[tmp])
            {
                vis[tmp]=true;
                que[r].pre=l;
                que[r].ch=a[i]+'0';
                if(tmp==0)
                {
                    getstr(r);
                    return true;
                }
                r++;
            }
        }
        l++;
    }
    return false;
}

bool cmp(const string& a,const string &b)
{
    if(a.size()==b.size()) return a<b;
    return a.size()<b.size();
}

int main()
{
    while(scanf("%d",&n),n)
    {
        if(n<=11)//11之前直接输出    可以减少bfs的判断
        {
            printf("%d\n",n);
            continue;
        }
        ans="";
        bool wokao=false;
        for(int i=1;i<10;i++)
        {
            a[0]=i;
            curans="";
            if(bfs(1))
                if(!wokao||cmp(curans,ans))//大小关系是未知的   必须加以判断
                {
                    wokao=true;
                    ans=curans;
                }
        }
        if(wokao)
            cout<<ans<<endl;
        else
        {
            for(int i=0;i<10;i++)
                for(int j=i+1;j<10;j++)
                {
                    a[0]=i,a[1]=j;
                    curans="";
                    if(bfs(2))
                        if(!wokao||cmp(curans,ans))
                        {
                            wokao=true;
                            ans=curans;
                        }
                }
            cout<<ans<<endl;
        }
    }
    return 0;
}
BFS

HDU 4634 Swipe Bo

Posted on

玛德 我现在特别想骂人 这道题真特么的坑爹 坑爹 坑爹 航电你就不能吧数据搞的好一点么 写了我几乎整整一天

我也不想多说什么了 真的 让我静静 这时间浪费的太不值了…………

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

char g[220][220];
int sx,sy,ex,ey;
int row,col,keynum;
bool flag[202][202][1<<7][4];
int mve[][2] = {{-1,0},{0,-1},{1,0},{0,1}};
struct node
{
    int key,num;
    int x,y;
    node(){}
    node(int _x,int _y,int change=0,int status=0):x(_x),y(_y),key(status),num(change) {}
};
int bfs()
{
    queue<node> que;
    node tmp,now;
    que.push(node(sx,sy));
    memset(flag,false,sizeof(flag));
    while(!que.empty())
    {
        tmp = que.front();
        que.pop();
        for(int i = 0; i < 4; i++)
        {
            int x = tmp.x;
            int y = tmp.y;
            int ss = tmp.key;
            int dir=i;
            while(1)
            {
                if(g[x][y] =='L') dir=1;
                if(g[x][y] == 'U') dir=0;
                if(g[x][y] == 'D') dir=2;
                if(g[x][y] == 'R') dir=3;
                if(flag[x][y][ss][dir])break;
                flag[x][y][ss][dir] = true;
                if(g[x][y]>='0'&&g[x][y]<'8')
                 ss |= (1<<(g[x][y]-'0'));
                if( x == ex && y== ey && ss ==keynum)
                    return tmp.num+1;
                if(x+mve[dir][0]>=0 && x+mve[dir][0]<row&& y+mve[dir][1]>=0 && y+mve[dir][1]<col)
                    if( g[x+mve[dir][0]][y+mve[dir][1]]=='#' )
                    {
                        que.push(node(x,y,tmp.num+1,ss));
                        break;
                    }
                    else
                    {
                        x+=mve[dir][0];
                        y+=mve[dir][1];
                    }
                else  break;
            }
        }
    }
    return -1;
}

int main()
{
    while(scanf("%d%d",&row,&col)!=EOF)
    {
        keynum = 0;
        for(int i = 0; i < row; i++)
        {
            scanf("%s",g[i]);
            for(int j = 0; j < col; j++)
                if(g[i][j] == 'S')
                    sx = i,sy = j;
                else if(g[i][j] == 'E')
                    ex = i,ey = j;
                else if(g[i][j] == 'K')
                    g[i][j]='0'+keynum++;
        }
        keynum=(1<<keynum)-1;
        printf("%d\n",bfs());
    }
    return 0;
}
DFS

HDU 4499 Cannon

Posted on

原创的思维和代码永远比看题解A的兴奋的多!

原创的思维和代码永远比看题解A的兴奋的多!!

原创的思维和代码永远比看题解A的兴奋的多!!!

原创的思维和代码永远比看题解A的兴奋的多!!!!

原创的思维和代码永远比看题解A的兴奋的多!!!!!

原创的思维和代码永远比看题解A的兴奋的多!!!!!!

哪怕算法效率上差别人很多

昨天的周常比赛我看到这题就知道用暴力回溯 想想应该和八皇后难度上差不了多少 就放到最后一小时再写 结果就懵逼了
越写越乱 最后也没写出来 晚上也一直在想 结果发现 越深究,我的思路漏洞越多,这个问题也变得越来越有趣,今天早上还是被我A了 真是痛快
思路就是暴力回溯 具体的 见注释(其实我不建议你看我代码,因为我觉得太臭了,但毕竟是自己亲生的,哈哈哈哈哈哈哈哈哈哈

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int ans,row,col;
int mat[10][10];//整个棋盘我分为4种状态  0 空   1  其他棋子   2  放炮排斥位置   3  炮

void update(int x,int y)
{
    bool flag=true;
    for(int i=y+1; i<col-1&&flag; i++)//对坐标右行进行更新
        if(mat[x][i]==1&&mat[x][i+1]==1) break;//遇到两个相邻的其他棋子就不需要了
        else if(mat[x][i]==1)//如果只是一个其他棋子
            for(int j=i+1; j<col; j++)
                if(mat[x][j]==1){flag=false;break;}//再碰到一个其他棋子
                else mat[x][j]=2;
    for(int i=0; i<y; i++)//对坐标坐标进行更新
        if(mat[x][i]==3&&mat[x][i+1]!=1&&mat[x][i+2]!=1)//如果前面有炮并且没有两个相邻的其他棋子阻隔   (其实这里还写不大好,抄了小路,既然A了就算了
            for(int j=y+1; j<col; j++)
                if(mat[x][j]==1) break;//碰到一个其他棋子
                else mat[x][j]=2;
    flag=true;
    for(int i=x+1; i<row-1&&flag; i++)
        if(mat[i][y]==1&&mat[i+1][y]==1) break;
        else if(mat[i][y]==1)
            for(int j=i+1; j<row; j++)
                if(mat[j][y]==1) {flag=false;break;}
                else mat[j][y]=2;
    for(int i=0; i<x; i++)
        if(mat[i][y]==3&&mat[i+1][y]!=1&&mat[i+2][y]!=1)
            for(int j=x+1; j<row; j++)
                if(mat[j][y]==1) break;
                else mat[j][y]=2;
}

void dfs(int r,int num,int add,int st)
{
    if(r==row)
    {
        ans=max(num,ans);
        return ;
    }
    int temprow[7],tempcol[7],tt;
    for(int i=st; i<col; i++)
    {
        if(mat[r][i]==0)
        {
            for(int j=0; j<col; j++)
                temprow[j]=mat[r][j];
            for(int j=0; j<row; j++)
                tempcol[j]=mat[j][i];
            tt=mat[r][i];//最傻最暴力的备份方法
            mat[r][i]=3;//放炮
            update(r,i);//更新
            if(add<2&&i<col-1) dfs(r,num+1,add+1,i+1); //对于一行来说   最多可以放3个炮  同行递归
            dfs(r+1,num+1,0,0);//同行递归不行就下一行
            mat[r][i]=tt;//还原
            for(int j=0; j<col; j++)
                mat[r][j]=temprow[j];
            for(int j=0; j<row; j++)
                mat[j][i]=tempcol[j];
        }
    }
    dfs(r+1,num,0,0);//也有可能我一正行都不能放反而更优
}

int main()
{
    int num,x,y;
    while(scanf("%d%d%d",&row,&col,&num)!=EOF)
    {
        memset(mat,0,sizeof mat);
        for(int i=0; i<num; i++)
        {
            scanf("%d%d",&x,&y);
            mat[x][y]=1;
        }
        ans=0;
        dfs(0,0,0,0);
        printf("%d\n",ans);
    }
    return 0;
}