admin管理员组

文章数量:1130349

Codeforces Round #354 (Div. 2) D. Theseus and labyrinth（bfs）

题意：给出一个n*m的地图，英雄从(xt,yt)出发，要到达敌人所在地(xm,ym)。地图每个格子有设定：

^>v<代表向箭头方向有门，其他方向没门；

URDL代表某个方向没门，其他方向都有门，例如U，代表上面没门，其他3个方向各有一个门。

-|代表左右有门、上下有门。

+代表4个门，*代表没有门。

每分钟，英雄可以进行一项操作：

A.将所有方块顺时针转90度。

B.移动到相邻方块，要求自己方块到它的方向有门，它的方块到自己的方向也有门。

给出地图、英雄位置、敌人位置，求英雄到达敌人的最少分钟数，或者不能到达输出-1。

题解：

走迷宫，典型的广搜题。广搜每个节点有5种扩展：旋转90度、往4个方向走。注意记录某个点是否走过，需要save[x][y][z]，x,y为该点坐标，z为旋转的次数，z<=3。

比较难写的是判断某个点能否向某个方向走一步，可以写到一个函数里can(x,y,z,j)，(x,y)为当前坐标，z为当前旋转了几次(0~3)，j为方向，我设定方向0123代表上右下左。

方块旋转、门的位置可以预处理，记到一个数组里，例如rot['<'][2] = '>'，代表<符号旋转2次得到>符号。

例如door['-'] = "0101"，代表-符号的门开在右、左。

这块写好了就无敌了。

（可恶，刚才看官方题解，哇，直接预处理出4种方向的地图，a[x][y][z]，就是简单的三维地图bfs了，卧槽，我怎么没想到）


//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;#define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE  freopen("D.in","r",stdin)
#define WE  freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {if(ed>=st)cout<<a[st];int i;FOR(i,st+1,ed)cout<<' '<<a[i];puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const double EPS=1e-10;
inline int sgn(double &x) {if(fabs(x) < EPS)return 0;if(x < 0)return -1;else return 1;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=1111;
const int MAXM=33;
const int MOD = 1000000007;
const int gx[4] = {-1,0,1,0};
const int gy[4] = {0,1,0,-1};
int n,m;
char s[MAXN][MAXN];
int xt,yt,xm,ym;int save[MAXN][MAXN][4];
char rota[222][4];
char door[222][5];
void init() {int i,j;MF1(save);REP(i,4) {rota['+'][i]='+';rota['*'][i]='*';}for(i=0; i<4; i+=2) {rota['-'][0+i]='-';rota['|'][0+i]='|';rota['-'][1+i]='|';rota['|'][1+i]='-';}char q[5] = "^>v<";char w[5] = "URDL";REP(i,4) {REP(j,4) {int l=(i+j)%4;rota[q[i]][j] = q[l];rota[w[i]][j] = w[l];}}REP(i,4) {door['+'][i]='1';door['*'][i]='0';door['|'][i]=door['-'][i]='0';}door['|'][0]=door['|'][2] = '1';door['-'][1]=door['-'][3] ='1';REP(i,4)REP(j,4) {door[q[i]][j]='0';door[w[i]][j]='1';}REP(i,4) {door[q[i]][i]='1';door[w[i]][i]='0';}
}char rot(char x, int n) {return rota[x][n%4];
}bool cango(char now , char next, int j) {int k = (j+2)%4;
//    door[now][4]='\0';
//    door[next][4]='\0';
//    printf("%c,%c,%s,%s,%d,%d,%c,%c\n",now,next,door[now],door[next],j,k,door[now][j],door[next][k]);if (door[now][j]=='1' && door[next][k]=='1')return true;else return false;
}bool can(int x,int y,int z,int j) {int xx=x+gx[j];int yy=y+gy[j];if(xx<0 || xx>=n || yy<0 || yy>=m)return false;char now = s[x][y];char next = s[xx][yy];
//    printf("%c,%c %d->",now,next,z);now = rot(now, z);next = rot(next,z);
//    printf("%c,%c\n",now,next);if(cango(now,next,j))return true;else return false;
}struct Node {int x,y,z;int step;Node() {}Node(int _x,int _y,int _z,int _s) {x=_x;y=_y;z=_z;step=_s;}
};int farm() {deque<Node> d;int i,j;d.clear();d.push_back(Node(xt,yt,0,0));save[xt][yt][0]=0;while(!d.empty()) {Node now = d.front();int x=now.x, y=now.y, z=now.z, step=now.step;d.pop_front();
//        if(x==19 && z==1)printf("%d,%d,%d,%d\n",x,y,z,step);if(x==xm && y==ym)return step;int k = (z+1)%4;if(save[x][y][k]==-1 || save[x][y][k]>step+1) {d.push_back(Node(x, y, k, step+1));save[x][y][k]=step+1;}REP(i,4) {int xx=x+gx[i];int yy=y+gy[i];
//            printf("%d,%d,%d,%d,%d,[%d,%d,%d],%d\n",x,y,z,i,can(x,y,z,i),xx,yy,z,save[xx][yy][z]);if(can(x,y,z,i)&&(save[xx][yy][z]==-1 || save[xx][yy][z]>step+1)) {d.push_back(Node(xx,yy,z,step+1));save[xx][yy][z]=step+1;}}}return -1;
}int main() {int i;init();RD2(n,m);REP(i,n)scanf(" %s",s[i]);RD2(xt,yt);RD2(xm,ym);xt--;yt--;xm--;ym--;WN(farm());return 0;
}


Codeforces Round #354 (Div. 2) D. Theseus and labyrinth（bfs）

题意：给出一个n*m的地图，英雄从(xt,yt)出发，要到达敌人所在地(xm,ym)。地图每个格子有设定：

^>v<代表向箭头方向有门，其他方向没门；

URDL代表某个方向没门，其他方向都有门，例如U，代表上面没门，其他3个方向各有一个门。

-|代表左右有门、上下有门。

+代表4个门，*代表没有门。

每分钟，英雄可以进行一项操作：

A.将所有方块顺时针转90度。

B.移动到相邻方块，要求自己方块到它的方向有门，它的方块到自己的方向也有门。

给出地图、英雄位置、敌人位置，求英雄到达敌人的最少分钟数，或者不能到达输出-1。

题解：

走迷宫，典型的广搜题。广搜每个节点有5种扩展：旋转90度、往4个方向走。注意记录某个点是否走过，需要save[x][y][z]，x,y为该点坐标，z为旋转的次数，z<=3。

比较难写的是判断某个点能否向某个方向走一步，可以写到一个函数里can(x,y,z,j)，(x,y)为当前坐标，z为当前旋转了几次(0~3)，j为方向，我设定方向0123代表上右下左。

方块旋转、门的位置可以预处理，记到一个数组里，例如rot['<'][2] = '>'，代表<符号旋转2次得到>符号。

例如door['-'] = "0101"，代表-符号的门开在右、左。

这块写好了就无敌了。

（可恶，刚才看官方题解，哇，直接预处理出4种方向的地图，a[x][y][z]，就是简单的三维地图bfs了，卧槽，我怎么没想到）


//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;#define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE  freopen("D.in","r",stdin)
#define WE  freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {if(ed>=st)cout<<a[st];int i;FOR(i,st+1,ed)cout<<' '<<a[i];puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const double EPS=1e-10;
inline int sgn(double &x) {if(fabs(x) < EPS)return 0;if(x < 0)return -1;else return 1;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=1111;
const int MAXM=33;
const int MOD = 1000000007;
const int gx[4] = {-1,0,1,0};
const int gy[4] = {0,1,0,-1};
int n,m;
char s[MAXN][MAXN];
int xt,yt,xm,ym;int save[MAXN][MAXN][4];
char rota[222][4];
char door[222][5];
void init() {int i,j;MF1(save);REP(i,4) {rota['+'][i]='+';rota['*'][i]='*';}for(i=0; i<4; i+=2) {rota['-'][0+i]='-';rota['|'][0+i]='|';rota['-'][1+i]='|';rota['|'][1+i]='-';}char q[5] = "^>v<";char w[5] = "URDL";REP(i,4) {REP(j,4) {int l=(i+j)%4;rota[q[i]][j] = q[l];rota[w[i]][j] = w[l];}}REP(i,4) {door['+'][i]='1';door['*'][i]='0';door['|'][i]=door['-'][i]='0';}door['|'][0]=door['|'][2] = '1';door['-'][1]=door['-'][3] ='1';REP(i,4)REP(j,4) {door[q[i]][j]='0';door[w[i]][j]='1';}REP(i,4) {door[q[i]][i]='1';door[w[i]][i]='0';}
}char rot(char x, int n) {return rota[x][n%4];
}bool cango(char now , char next, int j) {int k = (j+2)%4;
//    door[now][4]='\0';
//    door[next][4]='\0';
//    printf("%c,%c,%s,%s,%d,%d,%c,%c\n",now,next,door[now],door[next],j,k,door[now][j],door[next][k]);if (door[now][j]=='1' && door[next][k]=='1')return true;else return false;
}bool can(int x,int y,int z,int j) {int xx=x+gx[j];int yy=y+gy[j];if(xx<0 || xx>=n || yy<0 || yy>=m)return false;char now = s[x][y];char next = s[xx][yy];
//    printf("%c,%c %d->",now,next,z);now = rot(now, z);next = rot(next,z);
//    printf("%c,%c\n",now,next);if(cango(now,next,j))return true;else return false;
}struct Node {int x,y,z;int step;Node() {}Node(int _x,int _y,int _z,int _s) {x=_x;y=_y;z=_z;step=_s;}
};int farm() {deque<Node> d;int i,j;d.clear();d.push_back(Node(xt,yt,0,0));save[xt][yt][0]=0;while(!d.empty()) {Node now = d.front();int x=now.x, y=now.y, z=now.z, step=now.step;d.pop_front();
//        if(x==19 && z==1)printf("%d,%d,%d,%d\n",x,y,z,step);if(x==xm && y==ym)return step;int k = (z+1)%4;if(save[x][y][k]==-1 || save[x][y][k]>step+1) {d.push_back(Node(x, y, k, step+1));save[x][y][k]=step+1;}REP(i,4) {int xx=x+gx[i];int yy=y+gy[i];
//            printf("%d,%d,%d,%d,%d,[%d,%d,%d],%d\n",x,y,z,i,can(x,y,z,i),xx,yy,z,save[xx][yy][z]);if(can(x,y,z,i)&&(save[xx][yy][z]==-1 || save[xx][yy][z]>step+1)) {d.push_back(Node(xx,yy,z,step+1));save[xx][yy][z]=step+1;}}}return -1;
}int main() {int i;init();RD2(n,m);REP(i,n)scanf(" %s",s[i]);RD2(xt,yt);RD2(xm,ym);xt--;yt--;xm--;ym--;WN(farm());return 0;
}


本文标签： Codeforces Round 354 (Div 2) D Theseus and labyrinth（bfs）

版权声明：本文标题：Codeforces Round #354 (Div. 2) D. Theseus and labyrinth（bfs） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://it.en369.cn/IT/1694655573a254594.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。