算法总结——深度优先搜索进阶2

program_xwl · 2024-07-31 12:54:20 · 算法·理论

由于深度优先搜索的原理和构造过于简单，直接开始讲题。

T1 上学路线

这...严格来说不是深搜吧。

思路：

记忆化搜索三步法，走起：

确定状态： \operatorname{dfs}(x,y) 代表从点 (1,1) 到达点 (x,y) 点的方案数。
状态转移：根据题意一个点要么从西方来，要么从南方来。于是该点的答案就是从西方来和从南方来的方案数之和。也就是 \operatorname{dfs}(x,y) = \operatorname{dfs}(x,y+1)+\operatorname{dfs}(x+1,y)
边界条件：有两种情况是非法的，需要输出 0 ，一是这个点正在维修，按照题意无法通行；二是跑出边界。特别的，从起点到地点有一种方案。
代码：
```
#include <bits/stdc++.h>
using namespace std;
```

long long n,m,k,ans[25][25]; bool mp[25][25];

long long dfs(long long x,long long y) { if(ans[x][y] != -1) return ans[x][y]; if(mp[x][y]) return ans[x][y] = 0; if(x == n && y == m) return ans[x][y] = 1; if(x == n) return ans[x][y] = dfs(x,y+1); if(y == m) return ans[x][y] = dfs(x+1,y); return ans[x][y] = dfs(x+1,y)+dfs(x,y+1); }

int main(void) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(ans,-1,sizeof(ans)); cin >> n >> m >> k; for(long long i = 1;i <= k;i++) { long long x,y; cin >> x >> y; mp[x][y] = 1; } cout << dfs(1,1); return 0; }

## T2 [宿舍里的故事之五子棋](https://www.luogu.com.cn/problem/P1479)
一定要看清楚，题目是说“输出所有可能的 $k$ 值的和”
### 思路：
一个点只有放子和不放子两种状态，时间复杂度是 $O(2^{n^2})$ 虽然很恐怖，但题目的数据范围允许这种简单粗暴的方法。
### 代码：
```cpp
#include <bits/stdc++.h>
using namespace std;

int n,sum = 0;
bool vis[6][6],visk[15];

int getk(void)
{
    int cnt = 0;
    for(int i = 1;i <= 5;i++)
    {
        bool flag = 1;
        for(int j = 1;j <= 5;j++)
        {
            if(vis[i][j] == 0)
            {
                flag = 0;
                break;
            }
        }
        if(flag) cnt++;
    }
    for(int j = 1;j <= 5;j++)
    {
        bool flag = 1;
        for(int i = 1;i <= 5;i++)
        {
            if(vis[i][j] == 0)
            {
                flag = 0;
                break;
            }
        }
        if(flag) cnt++;
    }
    bool flag = 1;
    for(int i = 1;i <= 5;i++)
    {
        if(vis[i][i] == 0)
        {
            flag = 0;
            break;
        }
    }
    if(flag) cnt++;
    flag = 1;
    for(int i = 1;i <= 5;i++)
    {
        if(vis[i][5-i+1] == 0)
        {
            flag = 0;
            break;
        }
    }
    if(flag) cnt++;
    return cnt;
}

void dfs(int x,int y,int cnt)
{
    if(cnt > n) return;
    if(x > 5)
    {
        if(cnt == n)
        {
            int thek = getk();
            if(visk[thek] == 0)
            {
                sum += thek;
                visk[thek] = 1;
            }
        }
        return;
    }
    vis[x][y] = 1;
    if(y == 5) dfs(x+1,1,cnt+1);
    else dfs(x,y+1,cnt+1);
    vis[x][y] = 0;
    if(y == 5) dfs(x+1,1,cnt);
    else dfs(x,y+1,cnt);
}

int main(void)
{
    cin >> n;
    dfs(1,1,0);
    cout << sum;
    return 0;
}

T3 L国的战斗之伞兵

要不是这题爆 0 ，我可以进前三。

思路：

枚举每个点，用搜索按照该点的风向去往的点是否可以到达五峰区，这里可以用类似记忆化搜索的原理，用 ans_{i,j} 代表点 (i,j) 是否可以飞到无风区。这样时间很优。\ 但是，这题最坑的地方来了，就是它可以是一个圈，地图如下：

R	D
U	L

如果你没有开另一个 vis 数组来判断它是否走了重复的路，那么你的函数会在这张地图中一直转圈，因为它既不会出界也不会到无风区，再加上这题数据强大，你将一分不得。~~我就是这里丢了 100 分~~。所以，你要在前往目标格子时要标上另开的一个 vis 数组。

代码：

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

int n,m,cnt = 0;
char mp[1005][1005];
bool ans[1005][1005],vis[1005][1005];

bool dfs(int x,int y)
{
    if(x < 1 || y < 1 || x > n || y > m) return 0;
    if(ans[x][y]) return 1;
    if(vis[x][y]) return 0;
    if(mp[x][y] == 'u')
    {
        return ans[x][y] = dfs(x-1,y);
    }
    vis[x][y] = 1;
    if(mp[x][y] == 'd') return ans[x][y] = dfs(x+1,y);
    if(mp[x][y] == 'l') return ans[x][y] = dfs(x,y-1);
    if(mp[x][y] == 'r') return ans[x][y] = dfs(x,y+1);
    if(mp[x][y] == 'o') return ans[x][y] = 1;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            cin >> mp[i][j];
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(dfs(i,j)) cnt++;
        }
    }
    cout << cnt;
    return 0;
}

T4 单词方阵

思路：

这题都是固定的一个单词，可以暴力判断八个方向，也就 223 行而已吧。

代码：

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

int n;
char mp[105][105];
bool vis[105][105];

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            cin >> mp[i][j];
        }
    }
    for(int i = 1;i <= n-6;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if(
            mp[i][j] == 'y' &&
            mp[i+1][j] == 'i' &&
            mp[i+2][j] == 'z' &&
            mp[i+3][j] == 'h' &&
            mp[i+4][j] == 'o' &&
            mp[i+5][j] == 'n' &&
            mp[i+6][j] == 'g'
            )
            {
                vis[i][j] = 1;
                vis[i+1][j] = 1;
                vis[i+2][j] = 1;
                vis[i+3][j] = 1;
                vis[i+4][j] = 1;
                vis[i+5][j] = 1;
                vis[i+6][j] = 1;
            }
        }
    }
    for(int i = 6;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if(
            mp[i][j] == 'y' &&
            mp[i-1][j] == 'i' &&
            mp[i-2][j] == 'z' &&
            mp[i-3][j] == 'h' &&
            mp[i-4][j] == 'o' &&
            mp[i-5][j] == 'n' &&
            mp[i-6][j] == 'g'
            )
            {
                vis[i][j] = 1;
                vis[i-1][j] = 1;
                vis[i-2][j] = 1;
                vis[i-3][j] = 1;
                vis[i-4][j] = 1;
                vis[i-5][j] = 1;
                vis[i-6][j] = 1;
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n-6;j++)
        {
            if(
            mp[i][j] == 'y' &&
            mp[i][j+1] == 'i' &&
            mp[i][j+2] == 'z' &&
            mp[i][j+3] == 'h' &&
            mp[i][j+4] == 'o' &&
            mp[i][j+5] == 'n' &&
            mp[i][j+6] == 'g'
            )
            {
                vis[i][j] = 1;
                vis[i][j+1] = 1;
                vis[i][j+2] = 1;
                vis[i][j+3] = 1;
                vis[i][j+4] = 1;
                vis[i][j+5] = 1;
                vis[i][j+6] = 1;
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 6;j <= n;j++)
        {
            if(
            mp[i][j] == 'y' &&
            mp[i][j-1] == 'i' &&
            mp[i][j-2] == 'z' &&
            mp[i][j-3] == 'h' &&
            mp[i][j-4] == 'o' &&
            mp[i][j-5] == 'n' &&
            mp[i][j-6] == 'g'
            )
            {
                vis[i][j] = 1;
                vis[i][j-1] = 1;
                vis[i][j-2] = 1;
                vis[i][j-3] = 1;
                vis[i][j-4] = 1;
                vis[i][j-5] = 1;
                vis[i][j-6] = 1;
            }
        }
    }
    for(int i = 1;i <= n-6;i++)
    {
        for(int j = 1;j <= n-6;j++)
        {
            if(
            mp[i][j] == 'y' &&
            mp[i+1][j+1] == 'i' &&
            mp[i+2][j+2] == 'z' &&
            mp[i+3][j+3] == 'h' &&
            mp[i+4][j+4] == 'o' &&
            mp[i+5][j+5] == 'n' &&
            mp[i+6][j+6] == 'g'
            )
            {
                vis[i][j] = 1;
                vis[i+1][j+1] = 1;
                vis[i+2][j+2] = 1;
                vis[i+3][j+3] = 1;
                vis[i+4][j+4] = 1;
                vis[i+5][j+5] = 1;
                vis[i+6][j+6] = 1;
            }
        }
    }
    for(int i = 6;i <= n;i++)
    {
        for(int j = 1;j <= n-6;j++)
        {
            if(
            mp[i][j] == 'y' &&
            mp[i-1][j+1] == 'i' &&
            mp[i-2][j+2] == 'z' &&
            mp[i-3][j+3] == 'h' &&
            mp[i-4][j+4] == 'o' &&
            mp[i-5][j+5] == 'n' &&
            mp[i-6][j+6] == 'g'
            )
            {
                vis[i][j] = 1;
                vis[i-1][j+1] = 1;
                vis[i-2][j+2] = 1;
                vis[i-3][j+3] = 1;
                vis[i-4][j+4] = 1;
                vis[i-5][j+5] = 1;
                vis[i-6][j+6] = 1;
            }
        }
    }
    for(int i = 1;i <= n-6;i++)
    {
        for(int j = 6;j <= n;j++)
        {
            if(
            mp[i][j] == 'y' &&
            mp[i+1][j-1] == 'i' &&
            mp[i+2][j-2] == 'z' &&
            mp[i+3][j-3] == 'h' &&
            mp[i+4][j-4] == 'o' &&
            mp[i+5][j-5] == 'n' &&
            mp[i+6][j-6] == 'g'
            )
            {
                vis[i][j] = 1;
                vis[i+1][j-1] = 1;
                vis[i+2][j-2] = 1;
                vis[i+3][j-3] = 1;
                vis[i+4][j-4] = 1;
                vis[i+5][j-5] = 1;
                vis[i+6][j-6] = 1;
            }
        }
    }
    for(int i = 6;i <= n;i++)
    {
        for(int j = 6;j <= n;j++)
        {
            if(
            mp[i][j] == 'y' &&
            mp[i-1][j-1] == 'i' &&
            mp[i-2][j-2] == 'z' &&
            mp[i-3][j-3] == 'h' &&
            mp[i-4][j-4] == 'o' &&
            mp[i-5][j-5] == 'n' &&
            mp[i-6][j-6] == 'g'
            )
            {
                vis[i][j] = 1;
                vis[i-1][j-1] = 1;
                vis[i-2][j-2] = 1;
                vis[i-3][j-3] = 1;
                vis[i-4][j-4] = 1;
                vis[i-5][j-5] = 1;
                vis[i-6][j-6] = 1;
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if(vis[i][j]) cout << mp[i][j];
            else cout << '*';
        }
        cout << '\n';
    }
    return 0;
}

T5 [CERC2013] Draughts

思路：

只要看到一个白棋，就给他开一个 \operatorname{dfs} ，尝试去吃旁边的子，想吃到子，需要满足两个条件：

中间是一个黑子。
目标格点是空的。

一颗黑子不能吃第二次，但一个格点可以走第二次，所以要标记黑子，不能标记格点。

代码：

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

int T,maxi,stx,sty;
char mp[15][15];
bool vis[15][15];
const int dx[4] = {-1,-1,1,1};
const int dy[4] = {-1,1,-1,1};

bool check(int x,int y,int d)
{
    if(x+2*dx[d] > 10 || x+2*dx[d] < 1 && y+2*dy[d] > 10 || y+2*dy[d] < 1) return 0;
    if(mp[x+dx[d]][y+dy[d]] != 'B' || vis[x+dx[d]][y+dy[d]]) return 0;
    if(mp[x+2*dx[d]][y+2*dy[d]] != '#' && (stx != x+2*dx[d] || sty != y+2*dy[d])) return 0;
    return 1;
}

void dfs(int x,int y,int cnt)
{
    maxi = max(maxi,cnt);
    for(int i = 0;i < 4;i++)
    {
        if(check(x,y,i))
        {
            vis[x+dx[i]][y+dy[i]] = 1;
            dfs(x+2*dx[i],y+2*dy[i],cnt+1);
            vis[x+dx[i]][y+dy[i]] = 0;
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--)
    {
        for(int i = 1;i <= 10;i++)
        {
            for(int j = 1;j <= 10;j++)
            {
                cin >> mp[i][j];
            }
        }
        maxi = 0;
        for(int i = 1;i <= 10;i++)
        {
            for(int j = 1;j <= 10;j++)
            {
                if(mp[i][j] == 'W')
                {
                    memset(vis,0,sizeof(vis));
                    stx = i;
                    sty = j;
                    dfs(i,j,0);
                }
            }
        }
        cout << maxi << '\n';
    }
    return 0;
}

T6 取数游戏

思路：

除了要判断一下周围有没有数被选过了，其他几乎和T2一模一样。

代码：

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

int T,n,m,mp[15][15],maxi;
bool vis[15][15];

void dfs(int x,int y,int sum)
{
    if(x > n)
    {
        maxi = max(maxi,sum);
        return;
    }
    vis[x][y] = 0;
    if(y == m) dfs(x+1,1,sum);
    else dfs(x,y+1,sum);
    if(vis[x][y+1] == 0 &&
    vis[x+1][y] == 0 &&
    vis[x-1][y] == 0 &&
    vis[x][y-1] == 0 &&
    vis[x+1][y+1] == 0 &&
    vis[x-1][y+1] == 0 &&
    vis[x+1][y-1] == 0 &&
    vis[x-1][y-1] == 0
    )
    {
        vis[x][y] = 1;
        if(y == m) dfs(x+1,1,sum+mp[x][y]);
        else dfs(x,y+1,sum+mp[x][y]);
        vis[x][y] = 0;
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= m;j++)
            {
                cin >> mp[i][j];
            }
        }
        maxi = -1e9;
        dfs(1,1,0);
        cout << maxi << '\n';
    }
    return 0;
}