[洛谷 3956][NOIP2017普及组]棋盘

题目链接

https://www.luogu.org/problem/P3956

题解

考场上前两道题花了半个小时就解决了，就这道题卡了本蒟蒻两个小时时间。

听说其他人用的都是 SPFA，或者是 DFS+记忆化，这里放上一个本蒟蒻写的 BFS 的题解吧。

这道题 BFS 的方法并不难理解，每次从当前格向 $4$ 个方向进行扩展，扩展时需根据当前格颜色和目标格的颜色进行处理，并更新目标格的最优解。

但最终代码会很长（向 $4$ 个方向扩展，每次需要考虑 $3$ 种情况（目标格为白色、目标格颜色与当前格不同、目标格颜色与当前格相同），总共要判断 $12$ 种情况），考场上我写了 $160$ 多行，这应该是我写的最长的比赛代码了吧。

//考场上写的代码，所以有些丑
//各位dalao见谅
//注释是考完以后添加的
#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 0x3fffffff
using namespace std;
int m,n,map[105][105],cost[105][105];
struct zt
{
 int x,y,is_cc,money;
 //is_cc=is_changed_color，代表该格是否变过颜色
 //0代表没有变色（即该格本身有颜色）
 //其他数字表示该格由白色变为相应的颜色 
}que[100005];
int h=1,t=1;
void push(int x,int y,int is_cc,int money)//入队 
{
 que[t].x=x;
 que[t].y=y;
 que[t].is_cc=is_cc;
 que[t].money=money;
 t++;
}
void pop()//出队 
{
 h++;
}
int is_empty()//判空 
{
 return h==t;
}
void init()
{
 scanf("%d%d",&m,&n);
 for(int i=1;i<=m;i++)
  for(int j=1;j<=m;j++)
   cost[i][j]=INF;
 for(int i=1;i<=n;i++)
 {
  int x,y,c;
  scanf("%d%d%d",&x,&y,&c);
  map[x][y]=c+1;
  //颜色参数：0---无色，1---红色，2---黄色 
 }
}
int main()
{
 init();
 push(1,1,0,0);
 cost[1][1]=0;
 for(int i=1;!is_empty();i++)//广搜，貌似h并没有什么卵用 
 { 
  int x=que[i].x,y=que[i].y,is_cc=que[i].is_cc,money=que[i].money;
  if(money>cost[x][y])continue;//剪枝
  if(x!=m&&((is_cc&&map[x+1][y])||(!is_cc)))//向下
  //is_cc&&map[x+1][y]代表当前格为白色，且要扩展的格有颜色（不能连续走过两个白色格）
  //!is_cc代表该格没变颜色（即不是白色格），可以任意扩展。 
  {
   if((!map[x+1][y]))//白色格
   {
    if(money+2<cost[x+1][y])
    {
     push(x+1,y,map[x][y],money+2);//显然，将白色格变为与当前格颜色相同的格子可以节省开支
     cost[x+1][y]=money+2;//更新最优解
    }
   }
   else if((is_cc?is_cc:map[x][y])!=map[x+1][y])//不同颜色格
   {
    if(money+1<cost[x+1][y])
    {
     push(x+1,y,0,money+1);
     cost[x+1][y]=money+1;
    }
   }
   else//相同颜色格
   {
    if(money<cost[x+1][y])
    {
     push(x+1,y,0,money);
     cost[x+1][y]=money;
    }
   }
  }
  //以下代码结构与上面相同
  //没错，为了偷懒，考场上直接Ctrl+C，Ctrl+V了
  //并且因此出现了不少麻烦的事情
  //所以，请各位dalao不要在考场上学我这样作死
  if(x!=1&&((is_cc&&map[x-1][y])||(!is_cc)))//向上 
  {
   if((!map[x-1][y]))
   {
    if(money+2<cost[x-1][y])
    {
     push(x-1,y,map[x][y],money+2);
     cost[x-1][y]=money+2;
    }
   }
   else if((is_cc?is_cc:map[x][y])!=map[x-1][y])
   {
    if(money+1<cost[x-1][y])
    {
     push(x-1,y,0,money+1);
     cost[x-1][y]=money+1;
    }
   }
   else
   {
    if(money<cost[x-1][y])
    {
     push(x-1,y,0,money);
     cost[x-1][y]=money;
    }
   }
  }
  if(y!=m&&((is_cc&&map[x][y+1])||(!is_cc)))//向右 
  {
   if((!map[x][y+1]))
   {
    if(money+2<cost[x][y+1])
    {
     push(x,y+1,map[x][y],money+2);
     cost[x][y+1]=money+2;
    }
   }
   else if((is_cc?is_cc:map[x][y])!=map[x][y+1])
   {
    if(money+1<cost[x][y+1])
    {
     push(x,y+1,0,money+1);
     cost[x][y+1]=money+1;
    }
   }
   else 
   {
    if(money<cost[x][y+1])
    {
     push(x,y+1,0,money);
     cost[x][y+1]=money;
    }
   }
  }
  if(y!=1&&((is_cc&&map[x][y-1])||(!is_cc)))//向左 
  {
   if((!map[x][y-1]))
   {
    if(money+2<cost[x][y-1])
    {
     push(x,y-1,map[x][y],money+2);
     cost[x][y-1]=money+2;
    }
   }
   else if((is_cc?is_cc:map[x][y])!=map[x][y-1])
   {
    if(money+1<cost[x][y-1])
    {
     push(x,y-1,0,money+1);
     cost[x][y-1]=money+1;
    }
   }
   else
   {
    if(money<cost[x][y-1])
    {
     push(x,y-1,0,money);
     cost[x][y-1]=money;
    }
   }
  }
  pop();
 }
 if(cost[m][m]!=INF)printf("%d",cost[m][m]);
 else printf("-1");
 return 0;
}

（UPD 2019/08/19：当时还不会用常量数组来枚举方向…现在回来看这题发现代码应该短很多的…）