2296. 神殿 

(File IO): input:temple.in output:temple.out

时间限制: 1500 ms  空间限制: 524288 KB  具体限制  

题目描述

输入

输出

样例输入

样例输入12 2+**U1 1 2 2样例输入22 3<><><>1 1 2 1

样例输出

样例输出1-1样例输出24

数据范围限制

提示

 题目标中的特殊符号：<>^v+*|-

Solution

走迷宫是BFS的长项

而这一道题就是在走迷宫的基础上改动了一些规则而已

广度优先遍历的规则：

在访问完所有的第i层节点后，才会开始访问第i+1层节点

队列里只会有相邻两层的节点

对于这道题，我们首先要解决状态表示

我的做法是，用一个四维bool数组以及一个四位的int数组

bool dt[1001][1001][4][4];//   dt   x    y   rec doorint door[4]={
   1,2,3,0};

如注释所示，dt[x][y][rec][door]即表示坐标为（x，y）的房间里，此时状态为rec时，编号为door的门的状态

 

那么