蓝桥杯倒计时 36天-DFS练习2

黄金二叉树

思路一：递推做法

#include
using namespace std;

const int N = 1e5+10;

int A[N];
int B[N];
int n,sum;

int main( ){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>A[i];
  int left,right;
  for(int i=1;i<=n;i++){
    cin>>left;
    cin>>right;
    if(left>0)B[left]=B[i]+1;//如果节点 i 有左子节点，计算左子节点的黄金指数
    if(right>0)B[right]=B[i]-1;//如果节点 i 有右子节点，计算左子节点的黄金指数
    if(B[i]==0)sum+=A[i];//如果节点 i 黄金指数 为 0，将权重加起来
  }
  cout<<sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路二：利用 dfs 来搜索整个二叉树，黄金指数为 0，则求和权值。

#include
using namespace std;
const int N = 1e5+10;
int n;
int w[N],l[N],r[N];

int dfs(int u,int j,int k){
    int res = (j == k) ? w[u] : 0; //如果黄金指数为 0，加入权值
    if(l[u]!=-1)res += dfs(l[u],j+1,k);//如果有左节点，搜索左节点，黄金指数+1。
    if(r[u]!=-1)res += dfs(r[u],j,k+1);//如果有右节点，搜索右节点，黄金指数+1。
    return res;
}

int main( ){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
    cout<<dfs(1,0,0)<<'\n';
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

混沌之力2

思路：利用染色算法，把与源点能到达的点的颜色涂为 1，把与终点能到达的点的颜色涂为 2。如果终点颜色为 1 说明有路径。如果颜色不同，一个墙的四周有一个 1，一个 2，则把它破掉就能存在一个路径。通过 0|1=1,0|2=2,1|2=3来遍历四周来看是否符合条件的墙，涂色利用 dfs 来涂。

#include
using namespace std;
const int N = 1e3+10;
int n,m;
int x,y,x2,y2;
char mp[N][N];
int dx[ ]={1,0,-1,0},dy[ ] = {0,1,0,-1};
int colors[N][N];
//涂色
void dfs(int x,int y,int color){
    colors[x][y]=color;
    for(int i=0;i<4;i++){
        int nx = dx[i]+x,ny = dy[i]+y;
        if(nx<0||nx>=n||ny<0||ny>=m||colors[nx][ny]||mp[nx][ny]=='#')continue;
        dfs(nx,ny,color);
    }
}
//判断是否墙的四周至少有一个 1，一个 2
bool check(int x,int y){
    int color = 0;
    for(int i=0;i<4;i++){
        int nx = dx[i]+x,ny = dy[i]+y;
        if(nx<0||nx>=n||ny<0||ny>=m)continue;
        color |= colors[nx][ny];
    }
    return color == 3;
}
int main( ){
    cin>>n>>m;
    cin>>x>>y>>x2>>y2;
    x--,y--,x2--,y2--;
    for(int i=0;i<n;i++)cin>>mp[i];
    dfs(x,y,1);
    //源点能直接到达终点
    if(colors[x2][y2]==1){puts("Yes"),return 0;}//输出后一定要 return 返回
    dfs(x2,y2,2);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]=='#'){
                //墙是否间隔源点和终点
                if(check(i,j)){
                    puts("Yes"),return 0;//输出后一定要 return 返回
                }
            }
        }
    }
    //没有符合条件的答案
    puts("No");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51