题解 P3956 【棋盘】

这道题有这么多人发题解啊，我也来凑一凑热闹。 很明显，一个普通的BFS ``` int x,y,z; scanf("%d%d",&n,&ge); for(int i=1;i<=ge;++i){ scanf("%d%d%d",&x,&y,&z); a[x][y]=z+1; } ``` 这一段是输入，储存他们的颜色，在这里，我将两种颜色分别用1、2表示（为了方便将没图色的用0来表示），所以颜色的地方+1。a数组存的是地图上哪里的颜色是什么样的。 ``` struct edge{ int xx,yy,money,color; bool use; friend bool operator <(const edge &xxx,const edge &yyy){ return xxx.money>yyy.money; } }; ``` 对于我这种蒟蒻来说，BFS就离不开结构体。xx、yy：表示位置，money：在这一个点用了多少钱，color：所在点颜色，use这个点的有没有放过魔法（0及没有，1及有） 结构体中最重要的就是operator重载运算符了,需注意它的用法（实测无误） ``` void BFS(){ priority_queue<edge> Q;//优先队列 edge e; //第一个点初始化 e.xx=e.yy=1,e.money=e.use=0; e.color=a[1][1]; Q.push(e); b[1][1]=1; while(!Q.empty()){ edge t; t=Q.top();Q.pop(); for(int i=0;i<4;++i){//四个方向 edge news; news.xx=t.xx+wx[i],news.yy=t.yy+wy[i]; if(news.xx<1||news.yy<1||news.xx>n||news.yy>n||b[news.xx][news.yy]) continue; news.use=!t.use;//上一格没用则这一格用，上一格用魔法则这一格不用 if(a[news.xx][news.yy]==0){//看一下这一个是不是没有颜色 //如果没有颜色 if(news.use)//如果这一格用魔法 news.money=t.money+2,news.color=t.color,news.use=1; else continue;//不能用魔法，跳过。 } else{ //有颜色 if(news.use) news.use=0;//如果这一格要用魔法，则没必要用（反正有颜色了） if(a[news.xx][news.yy]==t.color)//颜色相同不要钱 news.money=t.money,news.color=a[news.xx][news.yy]; else//不相同要钱 news.money=t.money+1,news.color=a[news.xx][news.yy]; } b[news.xx][news.yy]=1;//走过了不能走 if(news.xx==n&&news.yy==n){//到达 printf("%d\n",news.money); return; } Q.push(news);//入队 } } printf("-1\n"); } ``` 这一段代码就是核心部分，四个方向分别走，b数组存有没有到过。（其它我已p了注释，请诸位dalao自行审阅） # CODE ``` #include<bits/stdc++.h> using namespace std; #define N 105 int a[N][N],n,ge; const int wx[5]={0,0,1,-1}; const int wy[5]={1,-1,0,0}; bool b[N][N]; struct edge{ int xx,yy,money,color; bool use; friend bool operator <(const edge &xxx,const edge &yyy){ return xxx.money>yyy.money; } }; void BFS(){ priority_queue<edge> Q; edge e; e.xx=e.yy=1,e.money=e.use=0; e.color=a[1][1]; Q.push(e); b[1][1]=1; while(!Q.empty()){ edge t; t=Q.top();Q.pop(); for(int i=0;i<4;++i){ edge news; news.xx=t.xx+wx[i],news.yy=t.yy+wy[i]; if(news.xx<1||news.yy<1||news.xx>n||news.yy>n||b[news.xx][news.yy]) continue; news.use=!t.use; if(a[news.xx][news.yy]==0){ if(news.use) news.money=t.money+2,news.color=t.color,news.use=1; else continue; } else{ if(news.use) news.use=0; if(a[news.xx][news.yy]==t.color) news.money=t.money,news.color=a[news.xx][news.yy]; else news.money=t.money+1,news.color=a[news.xx][news.yy]; } b[news.xx][news.yy]=1; if(news.xx==n&&news.yy==n){ printf("%d\n",news.money); return; } Q.push(news); } } printf("-1\n"); } int main(){ int x,y,z; scanf("%d%d",&n,&ge); for(int i=1;i<=ge;++i){ scanf("%d%d%d",&x,&y,&z); a[x][y]=z+1; } BFS(); return 0; } ``` 但是这样就真的可以了吗？如果你和上面的程序几乎一样，你就只有95分。 为什么？因为漏了起点是重点的情况，所以要加上一段： ``` if(n==1){ printf("0\n"); return 0; } ``` 谢谢