CF1065D Three Pieces
2024-09-30 17:24:26
题目描述：给出一个n*n的棋盘，棋盘上每个格子有一个值。你有一个子，要求将这个子从1移到n*n（去k时可以经过比k大的点）。
开局时它可以作为车，马，相（国际象棋）。每走一步耗费时间1。你也可以中途将它换为车，马，相（国际象棋），耗费时间1。
求最短时间，以及保证最短时间的最少替换次数。
题解：
一道恶心人的搜索题。对于每个点分为n*n*3种状态，表示当前已经经过1 ~ k，当前是车 / 马 / 相。
对于每个状态讨论做车 / 马 / 相怎么走，以及将它换成另外两种的情况。
代码（已经不想再写一遍了）：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 15
int n,mp[N][N],rx,ry,lx,ly;
int dis[N][N][N*N][],f[N][N][N*N][];
bool vis[N][N][N*N][];
struct node
{
int x,y,d,typ;
node(){}
node(int x,int y,int d,int typ):x(x),y(y),d(d),typ(typ){}
}tp;
queue<node>q;
int dx[]={-,-,-,-,,,,};
int dy[]={-,,-,,-,,-,};
void ins(int x,int y,int d,int t)
{
if(!vis[x][y][d][t])
{
vis[x][y][d][t]=;
q.push(node(x,y,d,t));
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
scanf("%d",&mp[i][j]);
if(mp[i][j]==)
{
rx=i,ry=j;
}else if(mp[i][j]==n*n)
{
lx=i,ly=j;
}
}
}
memset(dis,0x3f,sizeof dis);
memset(f,0x3f,sizeof f);
dis[rx][ry][][]=dis[rx][ry][][]=dis[rx][ry][][]=;
f[rx][ry][][]=f[rx][ry][][]=f[rx][ry][][]=;
q.push(node(rx,ry,,));q.push(node(rx,ry,,));q.push(node(rx,ry,,));
vis[rx][ry][][]=vis[rx][ry][][]=vis[rx][ry][][]=;
int x,y,d,t,tx,ty,dd;
while(!q.empty())
{
tp=q.front();
q.pop();
x=tp.x,y=tp.y,d=tp.d,t=tp.typ;
vis[x][y][d][t]=;
if(t==)
{
for(int i=;i<n;i++)
{
dd = d+(mp[i][y]==d+);
if(dis[i][y][dd][t]>dis[x][y][d][t]+)
{
dis[i][y][dd][t]=dis[x][y][d][t]+;
f[i][y][dd][t]=f[x][y][d][t];
ins(i,y,dd,t);
}else if(dis[i][y][dd][t]==dis[x][y][d][t]+)
{
if(f[i][y][dd][t]>f[x][y][d][t])
{
f[i][y][dd][t]=f[x][y][d][t];
ins(i,y,dd,t);
}
}
dd = d+(mp[x][i]==d+);
if(dis[x][i][dd][t]>dis[x][y][d][t]+)
{
dis[x][i][dd][t]=dis[x][y][d][t]+;
f[x][i][dd][t]=f[x][y][d][t];
ins(x,i,dd,t);
}else if(dis[x][i][dd][t]==dis[x][y][d][t]+)
{
if(f[x][i][dd][t]>f[x][y][d][t])
{
f[x][i][dd][t]=f[x][y][d][t];
ins(x,i,dd,t);
}
}
}
if(dis[x][y][d][]>dis[x][y][d][]+)
{
dis[x][y][d][]=dis[x][y][d][]+;
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}else if(dis[x][y][d][]==dis[x][y][d][]+)
{
if(f[x][y][d][]>f[x][y][d][]+)
{
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}
}
if(dis[x][y][d][]>dis[x][y][d][]+)
{
dis[x][y][d][]=dis[x][y][d][]+;
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}else if(dis[x][y][d][]==dis[x][y][d][]+)
{
if(f[x][y][d][]>f[x][y][d][]+)
{
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}
}
}else if(t==)
{
for(int i=;i<;i++)
{
tx = x+dx[i],ty = y+dy[i];
if(tx<||ty<||tx>=n||ty>=n)continue;
dd = d+(mp[tx][ty]==d+);
if(dis[tx][ty][dd][t]>dis[x][y][d][t]+)
{
dis[tx][ty][dd][t]=dis[x][y][d][t]+;
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}else if(dis[tx][ty][dd][t]==dis[x][y][d][t]+)
{
if(f[tx][ty][dd][t]>f[x][y][d][t])
{
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}
}
}
if(dis[x][y][d][]>dis[x][y][d][]+)
{
dis[x][y][d][]=dis[x][y][d][]+;
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}else if(dis[x][y][d][]==dis[x][y][d][]+)
{
if(f[x][y][d][]>f[x][y][d][]+)
{
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}
}
if(dis[x][y][d][]>dis[x][y][d][]+)
{
dis[x][y][d][]=dis[x][y][d][]+;
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}else if(dis[x][y][d][]==dis[x][y][d][]+)
{
if(f[x][y][d][]>f[x][y][d][]+)
{
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}
}
}else
{
for(int i=;x-i>=&&y-i>=;i++)
{
tx = x-i,ty = y-i;
dd = d+(mp[tx][ty]==d+);
if(dis[tx][ty][dd][t]>dis[x][y][d][t]+)
{
dis[tx][ty][dd][t]=dis[x][y][d][t]+;
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}else if(dis[tx][ty][dd][t]==dis[x][y][d][t]+)
{
if(f[tx][ty][dd][t]>f[x][y][d][t])
{
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}
}
}
for(int i=;x+i<n&&y-i>=;i++)
{
tx = x+i,ty = y-i;
dd = d+(mp[tx][ty]==d+);
if(dis[tx][ty][dd][t]>dis[x][y][d][t]+)
{
dis[tx][ty][dd][t]=dis[x][y][d][t]+;
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}else if(dis[tx][ty][dd][t]==dis[x][y][d][t]+)
{
if(f[tx][ty][dd][t]>f[x][y][d][t])
{
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}
}
}
for(int i=;x-i>=&&y+i<n;i++)
{
tx = x-i,ty = y+i;
dd = d+(mp[tx][ty]==d+);
if(dis[tx][ty][dd][t]>dis[x][y][d][t]+)
{
dis[tx][ty][dd][t]=dis[x][y][d][t]+;
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}else if(dis[tx][ty][dd][t]==dis[x][y][d][t]+)
{
if(f[tx][ty][dd][t]>f[x][y][d][t])
{
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}
}
}
for(int i=;x+i<n&&y+i<n;i++)
{
tx = x+i,ty = y+i;
dd = d+(mp[tx][ty]==d+);
if(dis[tx][ty][dd][t]>dis[x][y][d][t]+)
{
dis[tx][ty][dd][t]=dis[x][y][d][t]+;
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}else if(dis[tx][ty][dd][t]==dis[x][y][d][t]+)
{
if(f[tx][ty][dd][t]>f[x][y][d][t])
{
f[tx][ty][dd][t]=f[x][y][d][t];
ins(tx,ty,dd,t);
}
}
}
if(dis[x][y][d][]>dis[x][y][d][]+)
{
dis[x][y][d][]=dis[x][y][d][]+;
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}else if(dis[x][y][d][]==dis[x][y][d][]+)
{
if(f[x][y][d][]>f[x][y][d][]+)
{
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}
}
if(dis[x][y][d][]>dis[x][y][d][]+)
{
dis[x][y][d][]=dis[x][y][d][]+;
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}else if(dis[x][y][d][]==dis[x][y][d][]+)
{
if(f[x][y][d][]>f[x][y][d][]+)
{
f[x][y][d][]=f[x][y][d][]+;
ins(x,y,d,);
}
}
}
}
int ans = dis[lx][ly][n*n][],tk=f[lx][ly][n*n][];
if(dis[lx][ly][n*n][]<ans)
{
ans=dis[lx][ly][n*n][];
tk =f[lx][ly][n*n][];
}else if(dis[lx][ly][n*n][]==ans)
{
tk=min(tk,f[lx][ly][n*n][]);
}
if(dis[lx][ly][n*n][]<ans)
{
ans=dis[lx][ly][n*n][];
tk =f[lx][ly][n*n][];
}else if(dis[lx][ly][n*n][]==ans)
{
tk=min(tk,f[lx][ly][n*n][]);
}
printf("%d %d\n",ans,tk);
return ;
}
最新文章
- PL/SQL %TYPE和%ROWTYPE的区别【转】
- iOS(本地通知与远程通知)
- NDK SO 库开发与使用中的 ABI 构架选择
- JS调用WebService
- jquery一些方法
- 被spring和hibernate4逼疯
- 项目的敏捷开发方法（转自MBAlib）
- Linux中ifreq 结构体分析和使用 及其在项目中的简单应用
- NVL函数(NVL,NVL2,NULLIF,COALESCE)
- ROS探索总结（十五）——amcl（导航与定位）
- 安利一个vps,7美元/年。
- LINUX 安装扩展(笔记)
- @property专题
- Word或者WPS里证件照的背景底色和像素调整
- Java 编程下简介 Class 与类加载
- 查看python中已安装的包有哪些
- map用法小例子
- win10开启开发人员模式
- 织梦(Dedecms)select_soft_post.php页面变量未初始漏洞
- HDU3658—How many words