题目链接:题目链接

题意:一个n*m的区域,每个格子都有上下左右四个门,相邻的两个格子A可以通向B当且仅当A对B的门和B对A的门都打开,问从起点S到终点T需要的最短时间

#include<bits/stdc++.h>
using namespace std;
const int N=1003;
int n,m;
int sx,sy,tx,ty;
int dirx[]={1,-1,0,0};
int diry[]={0,0,1,-1};
char matrix[N][N];
bool visit[N][N][4];
char rotat[6][15]={{"+-|^><vLRUD*"},{"+|->v^<UDRL*"},{"+-|v<>^RLDU*"},{"+|-<^v>DULR*"}};
class node
{
public:
int x;
int y;
int angle;
int step;
public:
node(int x,int y,int a,int s):x(x),y(y),angle(a),step(s){}
};
int number(char c)
{
if(c=='+') return 0;
if(c=='-') return 1;
if(c=='|') return 2;
if(c=='^') return 3;
if(c=='>') return 4;
if(c=='<') return 5;
if(c=='v') return 6;
if(c=='L') return 7;
if(c=='R') return 8;
if(c=='U') return 9;
if(c=='D') return 10;
if(c=='*') return 11;
}
bool yestop(char c)
{
if(c=='+'||c=='|'||c=='^'||c=='L'||c=='R'||c=='D')
return 1;
return 0;
}
bool yesbottom(char c)
{
if(c=='+'||c=='|'||c=='v'||c=='L'||c=='R'||c=='U')
return 1;
return 0;
}
bool yesleft(char c)
{
if(c=='+'||c=='-'||c=='<'||c=='R'||c=='U'||c=='D')
return 1;
return 0;
}
bool yesright(char c)
{
if(c=='+'||c=='-'||c=='>'||c=='L'||c=='U'||c=='D')
return 1;
return 0;
}
bool in(int x,int y)
{
if(x<=0||x>n||y<=0||y>m)
return 0;
return 1;
}
queue<node> Q;
int bfs()
{
Q.push(node(sx,sy,0,0));
visit[sx][sy][0]=1;
while(!Q.empty())
{
node p=Q.front();
Q.pop();
if(p.x==tx&&p.y==ty)
return p.step;
for(int i=0;i<4;i++)
{
int nx=p.x+dirx[i];
int ny=p.y+diry[i];
switch(i)
{
case 0:
if(in(nx,ny)&&!visit[nx][ny][p.angle]&&yesbottom(rotat[p.angle][number(matrix[p.x][p.y])])
&&yestop(rotat[p.angle][number(matrix[nx][ny])]))
{
Q.push(node(nx,ny,p.angle,p.step+1));
visit[nx][ny][p.angle]=1;
}
break;
case 1:
if(in(nx,ny)&&!visit[nx][ny][p.angle]&&yestop(rotat[p.angle][number(matrix[p.x][p.y])])
&&yesbottom(rotat[p.angle][number(matrix[nx][ny])]))
{
Q.push(node(nx,ny,p.angle,p.step+1));
visit[nx][ny][p.angle]=1;
}
break;
case 2:
if(in(nx,ny)&&!visit[nx][ny][p.angle]&&yesright(rotat[p.angle][number(matrix[p.x][p.y])])
&&yesleft(rotat[p.angle][number(matrix[nx][ny])]))
{
Q.push(node(nx,ny,p.angle,p.step+1));
visit[nx][ny][p.angle]=1;
}
break;
case 3:
if(in(nx,ny)&&!visit[nx][ny][p.angle]&&yesleft(rotat[p.angle][number(matrix[p.x][p.y])])
&&yesright(rotat[p.angle][number(matrix[nx][ny])]))
{
Q.push(node(nx,ny,p.angle,p.step+1));
visit[nx][ny][p.angle]=1;
}
break;
}
}
p.angle=(p.angle+1)%4;
if(!visit[p.x][p.y][p.angle])
{
p.step++;
Q.push(node(p));
visit[p.x][p.y][p.angle]=1;
}
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",matrix[i]+1);
scanf("%d%d",&sx,&sy);
scanf("%d%d",&tx,&ty);
printf("%d\n",bfs());
}

最新文章

  1. 利用MVC的自定义过滤器FilterAttribute、IActionFilter、IExceptionFilter实现异常处理等功能
  2. C语言实现二叉树-03版
  3. 避免由于Windows Update自动安装安全补丁导致VM意外重启
  4. study note--(Education)
  5. css案例学习之层叠样式
  6. 鸟哥的linux私房菜学习-(五)Linux系统的在线求助man page与info page
  7. mycat安装与配置
  8. 网站集群架构(LVS负载均衡、Nginx代理缓存、Nginx动静分离、Rsync+Inotify全网备份、Zabbix自动注册全网监控)--技术流ken
  9. windows下搭建vue开发环境+IIS部署
  10. 下载jar包的网站
  11. 从MySQL Bug#67718浅谈B+树索引的分裂优化(转)
  12. luigi 学习
  13. django 关于视频播放
  14. Python中bisect的使用
  15. 《SQL Server 2008从入门到精通》--20180716
  16. Install OpenCV3.0 on Eclipse
  17. Session实例
  18. 咏南中间件增加HTTPS.SYS支持
  19. I/O的整体介绍
  20. 重新学习MySQL数据库9:Innodb中的事务隔离级别和锁的关系

热门文章

  1. poj-------------(2752)Seek the Name, Seek the Fame(kmp)
  2. Intellij IDEA 安装 Mybatis插件
  3. 再不用担心DataRow类型转换和空值了(使用扩展方法解决高频问题)
  4. springMVC系统异常处理及自定异常处理
  5. iOS开发零碎笔记
  6. 转:mysql 创建一个用户,指定一个数据库
  7. 重点关注之OData with List
  8. groupadd命令详解(实例)
  9. sql插入多条数据的sql语句
  10. NOIP2009解题报告