AcWing 116. 飞行员兄弟 DFS版

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 116. 飞行员兄弟 DFS版原题链接简单

作者：

optimjie , 2019-12-08 20:15:42 , 所有人可见 , 阅读 11185

63

27

第一次写时恢复现场的地方使用backup备份会出现问题，一直没有发现，再一位大佬（大佬的代码）的指点下终于知道了问题所在，看了他的代码知道恢复现场时可以再翻回来。

题中如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

只要DFS时先改变把手的状态就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 5;

char g[N][N];
vector<PII> ans, tmp;

void turn_one(int x, int y)
{
    if (g[x][y] == '+') g[x][y] = '-';
    else g[x][y] = '+';
}

void turn_all(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        turn_one(x, i);
        turn_one(i, y);
    }
    turn_one(x, y);
}

void dfs(int x, int y)
{
    // 如果说所有的把手都操作完了就看看冰箱能否打开
    if (x == 3 && y == 4)
    {
        bool success = true;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j <4; j++)
                if (g[i][j] == '+')
                {    
                    success = false;
                    goto end;
                }
        end:
        if (success)
            if (ans.empty() || tmp.size() < ans.size())
                ans = tmp;
        return;
    }
    // 判断边界，如果y出界了就往下一行移动
    if (y == 4) x++, y = 0;

    // 操作把手(x, y)
    turn_all(x, y);
    tmp.push_back({ x, y });
    dfs(x, y + 1);
    // 恢复现场
    tmp.pop_back();
    turn_all(x, y);

    // 不操作把手(x, y)
    dfs(x, y + 1);

}

int main()
{
    for (int i = 0; i < 4; i++) scanf("%s", g[i]);

    // 从(0, 0)开始DFS
    dfs(0, 0);

    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) 
        printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);

    return 0;
}

50 评论

包子云 2022-03-23 14:20

在任何编程语言中，都不建议使用 goto 语句。因为它使得程序的控制流难以跟踪，使程序难以理解和难以修改。任何使用 goto 语句的程序可以改写成不需要使用 goto 语句的写法。

348492156@qq.com 9个月前

太死板也不好，goto适用于跳出多重循环和debug，OS中也有很多goto

acwing_go 2023-03-08 13:35

飞行员兄弟，不开飞机，改开冰箱门了

陈叔健爱学习 2022-03-29 21:54

建议改为

void dfs(int x, int y)
{
    if (x == 3 && y == 4)
    {
        bool success = true;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j <4; j++)
                if (g[i][j] == '+')
                {    
                    success = false;
                    return;
                }
        if (success)
            if (ans.empty() || tmp.size() < ans.size())
                ans = tmp;
        return;
    }

做完这题就回老家结婚 2022-07-20 09:50

这里success=false;无效,直接这样写就行了

for(int i=0;i<4;i++)
    for(int j=0;j<4;j++)
        if(g[i][j]=='+')
            return;
if(ans.empty()||ans.size()>tmp.size())
    ans=tmp;
return;

不如原神 2023-01-05 20:56

8000+ms 啊，有没有更好的办法

abyssalfish 2023-02-21 10:00

https://www.acwing.com/solution/content/44927/
数学方法好像只要几十ms

dfs你是要毁了我吗 8个月前

兄弟们注意以下，用backup来还原的话，千万不要开成全局变量，要开在dfs内部，我调了好半天才发现问题

acwing_59277 10个月前

求问，为什么DFS的方法这么快？我用普通枚举的方法跑完所有测试数据大概需要5000多ms，用DFS的方法只需要1000多ms。

贩卖日落_ 11个月前

大佬，想问一下结束条件为什么是x==3&&y==4

acwing_3681 9个月前

因为g从（0,0）开始，最后一个开关应该是（3,3）操作完它y再加1之后进行dfs，dfs接收到的是（3,4）。即dfs接收到（3,4）时已经把所用开关都操作完了。

贩卖日落_ 9个月前回复了 acwing_3681 的评论

谢谢，大佬

acwing_4785 11个月前

大佬{x ,y} 这种写法是 make_pair(x, y) 的简化写法吗，从什么版本开始的编译器支持这种写法？

Q.Q 2023-01-26 21:25

简化版turn_all

void turn(int x,int y)
{
    for(int i= 0;i<4;i++)
    {
        g[x][i]=88-g[x][i];
        g[i][y]=88-g[i][y];
    }
    g[x][y]=88-g[x][y];
}

这道题不过如此 2022-12-06 16:34

👍

腾杨天下 2021-03-02 09:28

非常感谢！

LZX123123 7个月前

能过吗？

严_6 9个月前

不用备份也能过欸

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 5;
int n=4;
char g[N][N];
int ans = 999;
vector<PII> path;
void op(int x,int y){
    for(int i=0;i<4;i++){
        if(g[x][i]=='-') g[x][i]='+';
        else g[x][i]='-';
        if(g[i][y]=='-') g[i][y]='+';
        else g[i][y]='-';
    }
    if(g[x][y]=='-') g[x][y]='+';
    else g[x][y]='-';
}

void dfs(int x,int y,int res){
    //if(res>10) return;
    if(y==4) y=0,x++;
    if(x==4){
        //printf("555\n");
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                if(g[i][j]=='+') return;
        ans = min(ans,res);
        cout << ans << endl;
        for(auto i: path)
            printf("%d %d\n",i.first,i.second);
        return;
    }
    dfs(x,y+1,res);

    op(x,y);
    path.push_back({x+1,y+1});
    dfs(x,y+1,res+1);
    op(x,y);
    path.pop_back();

}

int main()
{
    for(int i=0;i<4;i++)
        cin >> g[i];
    dfs(0,0,0);


  //  for (int i = 0; i < n; i ++ )    cout << g[i]<<endl;
    return 0;
}

班级小助手 2022-04-01 14:13

你知道backup出了什么问题吗，我刚开始也是这做，发现过不了，用turn翻回来就能过了，这是为什么

一路顺风 2022-07-02 18:52

可以啊我试了下没问题啊看看你的代码

bhjohnny 2022-02-23 16:04

为什么这里恢复现场之后还要有不操作把手再dfs一个呢？之前做的全排列那种都是恢复现场就好了，不用再dfs一次，求解答~

去看凌晨的海 2022-02-25 08:01

全排列是每一个数都要选的所以就不用dfs不选的情况

acwing_zyy 2022-02-23 11:26

哥哥们，我想问下为什么不能先不操作后操作呢，直觉上这样好像可以的，虽然vector一直加元素，但有没有办法做到这样呢~

去看凌晨的海 2022-02-25 08:02

可以把不操作把手那步放在操作把手的前面的

acwing_zyy 2022-02-25 09:03 回复了去看凌晨的海的评论

但是vector里面不是只会增加元素吗，删除vector里的元素这个操作应该放在哪呢

去看凌晨的海 2022-02-25 09:15 回复了 acwing_zyy 的评论

不操作把手就不用往vector加元素删除的话是pop_back()

acwing_zyy 2022-02-25 12:55 回复了去看凌晨的海的评论

什么时候删除呢

去看凌晨的海 2022-02-25 18:33 回复了 acwing_zyy 的评论

因为不操作就不用加所以不用删除

acwing_zyy 2022-02-25 20:13 回复了去看凌晨的海的评论

 // 不操作把手(x, y)
    dfs(x, y + 1);
// 操作把手(x, y)
    turn_all(x, y);
    tmp.push_back({ x, y });
    dfs(x, y + 1);

这样是错的~

去看凌晨的海 2022-02-25 20:16 回复了 acwing_zyy 的评论

 // 不操作把手(x, y)
    dfs(x, y + 1);
// 操作把手(x, y)
    turn_all(x, y);
    tmp.push_back({ x, y });
    dfs(x, y + 1);
    tmp.pop_back() // 在这里删除 因为操作过了

acwing_zyy 2022-02-25 20:27 回复了去看凌晨的海的评论

不对，wa掉了TAT

去看凌晨的海 2022-02-26 08:54 回复了 acwing_zyy 的评论

   // 不操作把手(x, y)
    dfs(x, y + 1);

    // 操作把手(x, y)
    turn_all(x, y);
    tmp.push_back({ x, y });
    dfs(x, y + 1);
    // 恢复现场
    tmp.pop_back();
    turn_all(x, y);

你翻转的操作加了吗