NOIP2013华容道

现在的位置: 首页 > 综合 > 正文

RSS

2017年04月27日 ⁄ 综合 ⁄ 共 6740字 ⁄ 字号小中大 ⁄ 评论关闭

做了13年的题，发个题解卖卖萌。

货车运输就不再说了，倍增也很好写。

说一说华容道。

这道题相当的坑，谁会想到NOIP最后一道题会考宽搜。（我一开始想成双连通分量了。。。）

宽搜。

可以发现，棋子要移动的前提是：它的四周有一个空格。因此状态总共只有2种决策：要么棋子与空格交换，要么空格在棋子周围的四个格子中自由移动。宽搜写起来也很方便。

那么现在问题来了，一组数据有多组询问，普通的宽搜是肯定要超时的，怎么办呢？

仔细一看就会发现这道题的特点：所有的询问都是在同一张图上进行的，而这张图又很小（30*30）。所以我们可以先预处理出所有点周围的空格在不经过它的情况下互相能够到达的最短路，这样每一次宽搜就相当于跑一次最短路了。（当然用SPFA最方便啊）

啥都不说了，上代码;

①预处理最短路代码：

void pre_BFS(int sx,int sy)//预处理出(sx,sy)这个格子周围四个格子间不经过(sx,sy)的最短路
{
	
  for(int i=0;i<4;i++)
  {
  	int xx=sx+dx[i];
  	int yy=sy+dy[i];
  	
  	if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy])
  	{
  	  st.push((dog){xx,yy,i});
  	}
  	
  }
  
  while(!st.empty())//需要一个一个处理
  {
  
     while(!q.empty())q.pop();
  
     memset(dis,inf,sizeof(dis));
  
     int nx=st.top().x,ny=st.top().y,ret=st.top().now;
  
     dis[nx][ny]=0;
     
	 q.push((node){nx,ny});
	    
     st.pop();
  
     while(!q.empty())
     {
     	node u=q.front();q.pop();
     	
     	int x=u.x,y=u.y;
     	
     	for(int i=0;i<4;i++)
     	{
     		int xx=x+dx[i];
     		int yy=y+dy[i];
     		
     		if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]&&(xx!=sx||yy!=sy)&&dis[xx][yy]==inf)//由于路权都为1，所以第一次到达即为最短路 
     		{
     		  dis[xx][yy]=dis[x][y]+1;
			  q.push((node){xx,yy});  
     		}
     		
     	}
     	
     }
     
     for(int i=0;i<4;i++)
     {
     	int xx=sx+dx[i];
     	int yy=sy+dy[i];
     	
     	if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]&&(xx!=nx||yy!=ny)&&dis[xx][yy]!=inf)
     	{
     		step[sx][sy][ret][i]=dis[xx][yy];//记录最短路
     	}
     }
     
  }
  
}

②求解BFS

void pre_BLACK()//找当前的空格到棋子周围的空格的最短路 
{
   while(!q.empty())q.pop();
  
   memset(dis,inf,sizeof(dis));
   
   dis[EX][EY]=0;
   
   q.push((node){EX,EY});
   
   while(!q.empty())
   {
   	 node u=q.front();q.pop();
   	 
   	 for(int i=0;i<4;i++)
   	 {
   	 	int xx=u.x+dx[i];
     	int yy=u.y+dy[i];
     		
     	if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]&&(xx!=SX||yy!=SY)&&dis[xx][yy]==inf)//不能经过(SX,SY)这个点
     	{
     		dis[xx][yy]=dis[u.x][u.y]+1;
			q.push((node){xx,yy});  
     	}
   	 }
   	 
   }
   
  /*for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  	printf("dis[%d][%d]=%d\n",i,j,dis[i][j]);
  }*/
   
}

int BFS()//个人觉得叫SPFA()更合适些
{
	
  if(TX==SX&&TY==SY)return 0;//起点与终点重合，返回0
	
  pre_BLACK();//预处理
	
  memset(dp,inf,sizeof(dp));
	
  while(!Q.empty())Q.pop();
	
  for(int i=0;i<4;i++)
  {
  	int xx=SX+dx[i];
  	int yy=SY+dy[i];
  	
  	if(xx>0&&yy>0&&xx<=n&&yy<=m&&dis[xx][yy]!=inf&&map[xx][yy])
  	{
  	  dp[SX][SY][i]=dis[xx][yy];//加入队列
  	  Q.push((dog){SX,SY,i});
  	  inq[SX][SY][i]=1;
  	}
  	
  }
  
  while(!Q.empty())
  {
  	dog u=Q.front();Q.pop();
  	
  	inq[u.x][u.y][u.now]=0;
  	
  	/////////////////////棋子移到空格的情况
  	
  	int xx=u.x+dx[u.now];
  	int yy=u.y+dy[u.now];
  	
  	if(dp[xx][yy][(u.now+2)%4]>dp[u.x][u.y][u.now]+1)
  	{
  	  dp[xx][yy][(u.now+2)%4]=dp[u.x][u.y][u.now]+1;
  	  if(!inq[xx][yy][(u.now+2)%4])
  	  {
  	  	inq[xx][yy][(u.now+2)%4]=1;
  	  	Q.push((dog){xx,yy,(u.now+2)%4});
  	  }
  	}
  	
  	/////////////////////棋子周围的空格互相移动的情况
  	
  	for(int i=0;i<4;i++)
  	{
  	  xx=u.x+dx[i];
  	  yy=u.y+dy[i];
  	  
  	  if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]&&i!=u.now&&step[u.x][u.y][u.now][i]!=inf)
  	  {
  	  	if(dp[u.x][u.y][i]>dp[u.x][u.y][u.now]+step[u.x][u.y][u.now][i])
  	  	{
  	  		dp[u.x][u.y][i]=dp[u.x][u.y][u.now]+step[u.x][u.y][u.now][i];
  	  		if(!inq[u.x][u.y][i])
  	  		{
  	  			inq[u.x][u.y][i]=1;
  	  			Q.push((dog){u.x,u.y,i});
  	  		}
  	  	}
  	  }
  	  
  	}
  	
  }
  
  int ans=inf;
  
  for(int i=0;i<4;i++)//找最短路 
  {
  	ans=min(ans,dp[TX][TY][i]);
  }
  
  if(ans==inf)return -1;//不存在 
  return ans;
  
}

③主函数

int main()
{
  scanf("%d%d%d",&n,&m,&T);
  
  for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  	scanf("%d",&map[i][j]);
  }
  
  memset(step,inf,sizeof(step));
  
  for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  	if(map[i][j])pre_BFS(i,j);//预处理最短路
  }
  
  for(int i=1;i<=T;i++)
  {
  	scanf("%d%d%d%d%d%d",&EX,&EY,&SX,&SY,&TX,&TY);
  	
  	printf("%d\n",BFS());
  	
  }
  
  /*for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  	for(int k=0;k<4;k++)
  	{
  	  printf("dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k]);
  	}
  }*/
  
  return 0;
}

④头文件什么的

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<stack>
using namespace std;

const int inf=0x3f3f3f3f;

struct node
{
  int x,y;
};

struct dog//名字什么的不重要
{
  int x,y,now;
};

queue<node>q;

queue<dog>Q;

stack<dog>st;

int n,m,T,EX,EY,SX,SY,TX,TY;

int map[30+10][30+10],dis[30+10][30+10],step[30+10][30+10][5][5],inq[30+10][30+10][5];

int dp[30+10][30+10][4];

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

然后就A了。

惊奇的发现居然比标程快！！！

当然，这份代码是下来写的，考场上的暴力宽搜就不献丑了（只暴力了几十分）。

最后再贴一份完整代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<stack>
using namespace std;

const int inf=0x3f3f3f3f;

struct node
{
  int x,y;
};

struct dog
{
  int x,y,now;
};

queue<node>q;

queue<dog>Q;

stack<dog>st;

int n,m,T,EX,EY,SX,SY,TX,TY;

int map[30+10][30+10],dis[30+10][30+10],step[30+10][30+10][5][5],inq[30+10][30+10][5];

int dp[30+10][30+10][4];

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

void pre_BFS(int sx,int sy)//预处理出(sx,sy)这个格子周围四个格子间不经过(sx,sy)的最短路 
{
	
  for(int i=0;i<4;i++)
  {
  	int xx=sx+dx[i];
  	int yy=sy+dy[i];
  	
  	if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy])
  	{
  	  st.push((dog){xx,yy,i});
  	}
  	
  }
  
  while(!st.empty())//需要一个一个处理 
  {
  
     while(!q.empty())q.pop();
  
     memset(dis,inf,sizeof(dis));
  
     int nx=st.top().x,ny=st.top().y,ret=st.top().now;
  
     dis[nx][ny]=0;
     
	 q.push((node){nx,ny});
	    
     st.pop();
  
     while(!q.empty())
     {
     	node u=q.front();q.pop();
     	
     	int x=u.x,y=u.y;
     	
     	for(int i=0;i<4;i++)
     	{
     		int xx=x+dx[i];
     		int yy=y+dy[i];
     		
     		if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]&&(xx!=sx||yy!=sy)&&dis[xx][yy]==inf)//由于路权都为1，所以第一次到达即为最短路 
     		{
     		  dis[xx][yy]=dis[x][y]+1;
			  q.push((node){xx,yy});  
     		}
     		
     	}
     	
     }
     
     for(int i=0;i<4;i++)
     {
     	int xx=sx+dx[i];
     	int yy=sy+dy[i];
     	
     	if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]&&(xx!=nx||yy!=ny)&&dis[xx][yy]!=inf)
     	{
     		step[sx][sy][ret][i]=dis[xx][yy];//记录最短路 
     	}
     }
     
  }
  
}

void pre_BLACK()//找当前的空格到棋子周围的空格的最短路 
{
   while(!q.empty())q.pop();
  
   memset(dis,inf,sizeof(dis));
   
   dis[EX][EY]=0;
   
   q.push((node){EX,EY});
   
   while(!q.empty())
   {
   	 node u=q.front();q.pop();
   	 
   	 for(int i=0;i<4;i++)
   	 {
   	 	int xx=u.x+dx[i];
     	int yy=u.y+dy[i];
     		
     	if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]&&(xx!=SX||yy!=SY)&&dis[xx][yy]==inf)//不能经过(SX,SY)这个点 
     	{
     		dis[xx][yy]=dis[u.x][u.y]+1;
			q.push((node){xx,yy});  
     	}
   	 }
   	 
   }
   
  /*for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  	printf("dis[%d][%d]=%d\n",i,j,dis[i][j]);
  }*/
   
}

int BFS()//个人觉得叫SPFA()更合适些 
{
	
  if(TX==SX&&TY==SY)return 0;//起点与终点重合，返回0 
	
  pre_BLACK();//预处理 
	
  memset(dp,inf,sizeof(dp));
	
  while(!Q.empty())Q.pop();
	
  for(int i=0;i<4;i++)
  {
  	int xx=SX+dx[i];
  	int yy=SY+dy[i];
  	
  	if(xx>0&&yy>0&&xx<=n&&yy<=m&&dis[xx][yy]!=inf&&map[xx][yy])
  	{
  	  dp[SX][SY][i]=dis[xx][yy];//加入队列 
  	  Q.push((dog){SX,SY,i});
  	  inq[SX][SY][i]=1;
  	}
  	
  }
  
  while(!Q.empty())
  {
  	dog u=Q.front();Q.pop();
  	
  	inq[u.x][u.y][u.now]=0;
  	
  	/////////////////////棋子移到空格的情况 
  	
  	int xx=u.x+dx[u.now];
  	int yy=u.y+dy[u.now];
  	
  	if(dp[xx][yy][(u.now+2)%4]>dp[u.x][u.y][u.now]+1)
  	{
  	  dp[xx][yy][(u.now+2)%4]=dp[u.x][u.y][u.now]+1;
  	  if(!inq[xx][yy][(u.now+2)%4])
  	  {
  	  	inq[xx][yy][(u.now+2)%4]=1;
  	  	Q.push((dog){xx,yy,(u.now+2)%4});
  	  }
  	}
  	
  	/////////////////////棋子周围的空格互相移动的情况 
  	
  	for(int i=0;i<4;i++)
  	{
  	  xx=u.x+dx[i];
  	  yy=u.y+dy[i];
  	  
  	  if(xx>0&&yy>0&&xx<=n&&yy<=m&&map[xx][yy]&&i!=u.now&&step[u.x][u.y][u.now][i]!=inf)
  	  {
  	  	if(dp[u.x][u.y][i]>dp[u.x][u.y][u.now]+step[u.x][u.y][u.now][i])
  	  	{
  	  		dp[u.x][u.y][i]=dp[u.x][u.y][u.now]+step[u.x][u.y][u.now][i];
  	  		if(!inq[u.x][u.y][i])
  	  		{
  	  			inq[u.x][u.y][i]=1;
  	  			Q.push((dog){u.x,u.y,i});
  	  		}
  	  	}
  	  }
  	  
  	}
  	
  }
  
  int ans=inf;
  
  for(int i=0;i<4;i++)//找最短路 
  {
  	ans=min(ans,dp[TX][TY][i]);
  }
  
  if(ans==inf)return -1;//不存在 
  return ans;
  
}

int main()
{
  scanf("%d%d%d",&n,&m,&T);
  
  for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  	scanf("%d",&map[i][j]);
  }
  
  memset(step,inf,sizeof(step));
  
  for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  	if(map[i][j])pre_BFS(i,j);//预处理 
  }
  
  for(int i=1;i<=T;i++)
  {
  	scanf("%d%d%d%d%d%d",&EX,&EY,&SX,&SY,&TX,&TY);
  	
  	printf("%d\n",BFS());
  	
  }
  
  /*for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  	for(int k=0;k<4;k++)
  	{
  	  printf("dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k]);
  	}
  }*/
  
  return 0;
}

【上篇】POJ2706 Connect（并查集+模拟）
【下篇】Kitty’s Game

作者: Todedashyboob

该日志由 Todedashyboob 于7年前发表在综合分类下，最后更新于 2017年04月27日.
转载请注明: NOIP2013华容道 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

NOIP2013华容道

作者: Todedashyboob

书签

最新文章New

本站推荐

返回首页