Processing math: 0%

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

题目链接

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

题解

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

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

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

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//考场上写的代码,所以有些丑
//各位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;
}
//考场上写的代码,所以有些丑 //各位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; }
//考场上写的代码,所以有些丑
//各位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:当时还不会用常量数组来枚举方向…现在回来看这题发现代码应该短很多的…)

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理