啊，时间过得好快
学了1年编程，就从普及组退役了 //(ㄒoㄒ)//
还有200天就要参加恐怖的noip提高组 //(ㄒoㄒ)//
今天开始正式备战2019noip-TG
发两篇题解，记录我此时的水平
分别是
棋盘（就是这篇）（2017noip-PJ-T3）
瑞士轮（2011noip-PJ-T3）
maybe，我水平不止这点
这只说明了noip-PJ我只能AK前三道（自动过滤摆渡车）
以上纯属瞎扯，您可以从这儿开始看
原题链接（发题解好习惯^_^）
这明显是道搜索题
关于广搜
*他死了
（因为广搜是搜索“距离最近”，这里的金币不好控制，不过也有大佬写了广搜）
于是，我选择DFS
1 ≤ m ≤ 100
所以要记忆化
这道题其实不难
不过需要注意的是“加锁”和“解锁”是必要的
其实我第一遍打
因为对我的记忆化太自信了，认为不会走回路
所以没有用锁
后来发现初始sum=0的情况，是个漏洞
不用“锁”的话，前两个点就会来回
（可能这个问题对你而言并不是问题，我太菜了，第一遍没注意）
#include<bits/stdc++.h> using namespace std; int a[150][150],f[150][150];//a记录颜色 int n,m,i,j; bool p=false,b[150][150]; int dx[10]={0,1,0,0,-1}; int dy[10]={0,0,1,-1,0};//你懂得 void dfs(int x,int y,int sum,int cl,int op)//cl为当前位颜色，op记录某魔法是否施展 { if(x<1||y<1||x>n||y>m||b[x][y]) return; if(f[x][y]<=sum&&f[x][y]!=0) return; f[x][y]=sum;//记忆化，不然会TLE if(x==m&&y==m) { p=true;//有解 return; } b[x][y]=true;//加锁 for(int i=1;i<=4;i++) { int xx=x+dx[i],yy=y+dy[i]; //列举4种情况 if(a[xx][yy]==0) { if(op==1) continue; else dfs(xx,yy,sum+2,cl,1); } else { if(a[xx][yy]==cl) dfs(xx,yy,sum,cl,0); else dfs(xx,yy,sum+1,a[xx][yy],0); } } b[x][y]=false;//解锁 } int main() { cin>>m>>n; for(i=1;i<=n;i++) { int x,y,c; cin>>x>>y>>c; if(c==0)//red a[x][y]=1; if(c==1)//yellow a[x][y]=2; } dfs(1,1,0,a[1][1],0); if(!p) cout<<-1;//没有到达 else cout<<f[m][m]; return 0;//完美结束 }