2019 CCPC Harbin F-Fixing Banners

Description

给出6个字符串，问：是否能刚好从每个字符串上扣下一个字母组成‘harbin’

Analyze

最近看Dancing Links X，Dancing Links 据说是优化特殊DFS的一种数据结构，这里说的’特殊DFS’指：建模后是01矩阵，少选择几行，使每列有1。但这个题要求每行都必须选，就不是DLX算法了，只是简单的搜索。

Code

#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

string s;
int mp[10][10];
bool vis[10];

bool DFS(int deep)
{
    if(deep == 7)
        return 1;
    for(int i = 1; i <= 6; ++i)
        if(!vis[i] && mp[deep][i])
        {
            vis[i] = 1;
            if(DFS(deep +1))
                return 1;
            vis[i] = 0;
        }
    return 0;
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        memset(mp, 0, sizeof(mp));
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= 6; ++i)
        {
            cin >> s;
            if(s.find('h') != -1)
                mp[i][1] = 1;
            if(s.find('a') != -1)
                mp[i][2] = 1;
            if(s.find('r') != -1)
                mp[i][3] = 1;
            if(s.find('b') != -1)
                mp[i][4] = 1;
            if(s.find('i') != -1)
                mp[i][5] = 1;
            if(s.find('n') != -1)
                mp[i][6] = 1;
        }

        if(DFS(1))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

也是建模成01矩阵，然后DFS搜索：从每行选出一个字母，使得每列含1