7.26dfs周测复盘

DFS周测三题题解复盘

前言

本次周测覆盖了 DFS/BFS 的五大核心模型：

第一部分：P2089 烤鸡

基本信息

解题前・关键信号识别

解题后・外化复盘

AC 完整代码

#include<iostream>#include<vector>#include<string>#include<algorithm>usingnamespacestd;intn;intpath[10];vector<vector<int>>plans;voiddfs(intstep,intsum){if(sum>n)return;if(sum+(10-step)>n)return;if(sum+(10-step)*3<n)return;if(step==10){if(sum==n){plans.push_back(vector<int>(path,path+10));return;}}for(inti=1;i<=3;i++){path[step]=i;dfs(step+1,sum+i);}}intmain(){cin>>n;if(n<10||n>30){cout<<0<<endl;return0;}dfs(0,0);cout<<plans.size()<<endl;for(auto&p:plans){for(inti=0;i<10;i++){cout<<p[i]<<" ";}cout<<endl;}return0;}

第二部分：P1036 选数

基本信息

解题前・关键信号识别

解题后・外化复盘

AC 完整代码

#include<iostream>usingnamespacestd;intn,k,ans;inta[25];boolisPrime(intx){if(x<2)returnfalse;if(x==2)returntrue;if(x%2==0)returnfalse;for(inti=3;i*i<=x;i+=2){if(x%i==0)returnfalse;}returntrue;}voiddfs(intstep,intstart,intsum){if(step==k){if(isPrime(sum))ans++;return;}for(inti=start;i<n;i++){dfs(step+1,i+1,sum+a[i]);}}intmain(){cin>>n>>k;for(inti=0;i<n;i++){cin>>a[i];}dfs(0,0,0);cout<<ans<<endl;return0;}

第三部分：Perket

基本信息

解题前・关键信号识别

解题后・外化复盘

AC 完整代码

#include<iostream>#include<cmath>usingnamespacestd;intn;inta[15],b[15];intans=1e9;voiddfs(intstep,intsour,intbitter,boolchoose){if(step==n){if(choose){ans=min(ans,abs(sour-bitter));}return;}// 分支1：不选dfs(step+1,sour,bitter,choose);// 分支2：选dfs(step+1,sour*a[step],bitter+b[step],true);}intmain(){cin>>n;for(inti=0;i<n;i++){cin>>a[i]>>b[i];}dfs(0,1,0,false);cout<<ans<<endl;return0;}

三题对比总结

第四部分：填涂颜色（Flood Fill）

基本信息

解题前・关键信号识别

解题后・外化复盘

AC 完整代码

#include<iostream>#include<vector>#include<set>#include<cmath>#include<algorithm>usingnamespacestd;intn;intv[35][35];boolvis[35][35];intdx[]={-1,0,1,0};intdy[]={0,1,0,-1};voiddfs(intx,inty){if(x>=n||x<0||y>=n||y<0){return;}if(vis[x][y])return;if(v[x][y]!=0)return;vis[x][y]=true;for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];dfs(nx,ny);}}intmain(){cin>>n;for(inti=0;i<n;i++){for(intj=0;j<n;j++){cin>>v[i][j];}}for(inti=0;i<n;i++){dfs(i,0);dfs(i,n-1);}for(intj=0;j<n;j++){dfs(0,j);dfs(n-1,j);}for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(v[i][j]==0&&!vis[i][j]){cout<<2<<" ";}else{cout<<v[i][j]<<" ";}}cout<<endl;}return0;

第五部分：迷宫问题（BFS预处理）

基本信息

解题前・关键信号识别

解题后・外化复盘

AC 完整代码

#include<iostream>#include<vector>#include<queue>#include<cmath>#include<algorithm>usingnamespacestd;intn,m;string v[1005];intid[1005][1005];intcnt[1000005];intdx[]={-1,0,1,0};intdy[]={0,1,0,-1};voidbfs(intsx,intsy,intnum){queue<pair<int,int>>q;q.push({sx,sy});id[sx][sy]=num;intsize=0;while(!q.empty()){auto[x,y]=q.front();q.pop();size++;for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];if(nx<0||nx>=n||ny<0||ny>=n)continue;if(id[nx][ny])continue;if(v[x][y]==v[nx][ny])continue;id[nx][ny]=num;q.push({nx,ny});}}cnt[num]=size;}intmain(){cin>>n>>m;for(inti=0;i<n;i++){cin>>v[i];}intnum=0;for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(id[i][j]==0){num++;bfs(i,j,num);}}}while(m--){intx,y;cin>>x>>y;x--;y--;cout<<cnt[id[x][y]]<<endl;}return0;}