题解：P12782 [ICPC 2024 Yokohama R] E-Circuit Is Now on Sale!
题目大意
- 数字（0 到 9）：直接返回数字。
- 连接器（#）：一个输入，一个输出，直接传递值。
- 运算符（+，-，*，/）：对两个输入进行运算并输出结果。
- 打印机（P）：显示最终结果。
所有元件通过相邻连接形成一棵以打印机为根的树，我们需要计算这棵树的值。
解决方法
本题核心采用 DFS 遍历二维网格，核心逻辑是从根（打印机 P）出发，递归向下寻找子节点，根据元件类型执行对应逻辑，最终回溯返回计算结果，具体思路如下：
树的遍历起点：先在二维网格中找到打印机（P）的位置，以此作为 DFS 的起始节点（根节点）。
遍历规则：每个节点（元件）通过上下左右四个方向寻找子节点，需满足两个条件
-
位置有效（在网格内）；
-
不是父节点（避免回溯到上一级元件，防止环路）。
难点在于处理元件：
叶子节点：直接返回数值，终止当前分支的递归。
传递节点（#）：找到唯一的子节点，递归获取子节点结果并直接返回。
运算符：找到两个子节点，递归获取两个子节点结果后执行对应运算，返回运算结果。
根节点：找到唯一的子节点，递归获取整个表达式树的最终结果，作为输出。
代码实现
#include<bits/stdc++.h>
#define int long long//不开long long见祖宗
using namespace std;
int n,m;
vector<string>s;//字符数据
vector<vector<bool>>v;//标记数组
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};//方向数组
bool f(int x,int y){
return x>=0&&x<n&&y>=0&&y<m&&s[x][y]!='.';
}
//(xx,yy)为父节点
int dfs(int x,int y,int xx,int yy){
v[x][y]=true;
char c=s[x][y];
if(isdigit(c))return c-'0';//如果是数字，直接返回对应的数值
if(c=='#'){//连接器
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(f(nx,ny)&&!(nx==xx&&ny==yy)){//注意不能是父节点
return dfs(nx,ny,x,y);
}
}
}
if(c=='+'||c=='-'||c=='*'||c=='/'){//运算符
vector<int>q;//存储计算结果
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(f(nx,ny)&&!(nx==xx&&ny==yy)){
q.push_back(dfs(nx,ny,x,y));//计算子节点值并加入数组
}
}
int a=q[0],b=q[1];//两个子节点
if(c=='+')return a+b;
if(c=='-')return max(a,b)-min(a,b);
if(c=='*')return a*b;
return max(a,b)/min(a,b);
}
if(c=='P'){//打印机
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(f(nx,ny)){
return dfs(nx,ny,x,y);
}
}
}
}
signed main(){
cin>>n>>m;
s.resize(n+1);
v.assign(n+1,vector<bool>(m+1,false));
for(int i=0;i<n;i++){
cin>>s[i];
}
//找打印机
int px=-1,py=-1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i][j]=='P'){
px=i,py=j;break;
}
}
}
cout<<dfs(px,py,-1,-1);
return 0;
}时间复杂度：