@[Maysoul](/user/409774) 不解释代码意思谁给你看啊
by Bright1 @ 2023-04-16 09:45:50
@[stalx_awa](/user/741959)
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int num,ans=MAXN;
bool grid[110][110];
int vis[110][110];
int n,m;
int x,y,c;
struct point{
int r,c;
point()
{
r=0;c=0;
}
point(int ar,int cr)
{
r=ar,c=cr;
}
point friend operator + (point a,point b)
{
return point(a.r+b.r,a.c+b.c);
}
};
point offset[4]={point(0,1),point(0,-1),point(1,0),point(-1,0)};
void dfs(point cp,int coin,int color,bool flag)//当前点的坐标 当前金币数量 当前颜色 是否使用魔法
{
if (cp.r==m&&cp.c==m)//若到达终点，答案取金币的最小值
{
//cout<<coin<<" "<<color<<endl;
ans=min(ans,coin);
return;
}
for (int i=0;i<4;i++)
{
point np=cp+offset[i];//枚举四个点的坐标
if(0<np.r&&np.r<=m&&0<np.c&&np.c<=m&&grid[np.r][np.c]==0)//若当前格子未被走过
{
if(vis[np.r][np.c]==color)//若当前格子颜色相同，金币不变
{
grid[np.r][np.c]=1;
//cout<<"a"<<endl;
dfs(np,coin,color,0);
grid[np.r][np.c]=0;
}
else if(vis[np.r][np.c]!=-1)//若当前格子颜色不同 金币加一
{
grid[np.r][np.c]=1;
//cout<<"b"<<endl;
dfs(np,coin+1,vis[np.r][np.c],0);
grid[np.r][np.c]=0;
}
else if(flag==0) //若当前无色且未被走过
{
grid[np.r][np.c]=1;
//cout<<"c"<<endl;
dfs(np,coin+2,1,1);//染红色
dfs(np,coin+2,0,1);//染黄色
grid[np.r][np.c]=0;
}
}
}
}
int main()
{
memset(vis,-1,sizeof(vis));
cin>>m>>n;
int x,y,c;
for (int i=1;i<=n;i++)
{
cin>>x>>y>>c;
vis[x][y]=c;//记录棋盘颜色
}
grid[1][1]=1;
dfs(point(1,1),0,vis[1][1],0);//从起点开始DFS
if(ans==MAXN)
{
cout<<"-1"<<endl;
}
else
{
cout<<ans<<endl;
}
return 0;
}
```
感谢您的指出，已为您写出了DFS基本逻辑的注释，还请您不吝赐教
by Maysoul @ 2023-04-16 09:52:11
@[Maysoul](/user/409774) 这样存颜色，无色和红色都是0。
by Bright1 @ 2023-04-16 09:58:12
@[stalx_awa](/user/741959)
main里第一行memset(vis,-1,sizeof(vis));
无色的地方是-1
by Maysoul @ 2023-04-16 09:59:59
@[Maysoul](/user/409774) 若当前点无色，`vis[i][j]==color` 这两个都是 `-1`,那不就走不成也走了。
by Bright1 @ 2023-04-16 10:09:05
@[stalx_awa](/user/741959) color永远也不可能是-1呢亲
因为：
当color返回上一次的color的时候，上一次的color只可能是最初的color,颜色不同改变后的color,无色时的color
其中：
最初的color就是起点的颜色，数据保证起点有颜色
颜色不同改变后的color条件是vis[np.r][np.c]!=-1 所以它不会是-1
至于无色时 它只返回0和1，不会返回-1
by Maysoul @ 2023-04-16 10:15:10
@[stalx_awa](/user/741959) 怎么，写上注释也没人帮我看吗？
by Maysoul @ 2023-04-16 16:55:18
马上
by _Francis_ @ 2023-04-16 18:14:32
@[Maysoul](/user/409774) 现在有事
by _Francis_ @ 2023-04-16 18:14:53
@[Maysoul](/user/409774) 一方面是**没有剪枝**所以会超时，还有就是**逻辑上存在一点bug**，我等一下改一下
by _Francis_ @ 2023-04-16 18:42:26