{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540
{\fonttbl\f0\fnil\fcharset0 Consolas;\f1\fnil\fcharset0 Consolas-Italic;\f2\fnil\fcharset0 Consolas-Bold;
}
{\colortbl;\red255\green255\blue255;\red170\green170\blue170;\red236\green236\blue236;\red51\green51\blue51;
\red153\green153\blue137;\red255\green255\blue255;\red153\green153\blue153;\red72\green85\blue134;\red64\green151\blue151;
\red135\green20\blue16;\red195\green35\blue72;\red56\green133\blue176;}
\margl1440\margr1440\vieww9000\viewh8400\viewkind0
\deftab720
\itap1\trowd \taflags1 \trgaph108\trleft-108 \trbrdrt\brdrnil \trbrdrl\brdrnil \trbrdrt\brdrnil \trbrdrr\brdrnil
\clvertalc \clshdrawnil \clwWidth540\clftsWidth3 \clbrdrt\brdrnil \clbrdrl\brdrnil \clbrdrb\brdrnil \clbrdrr\brdrnil \gaph\cellx4320
\clvertalc \clshdrawnil \clwWidth14840\clftsWidth3 \clbrdrt\brdrnil \clbrdrl\brdrnil \clbrdrb\brdrnil \clbrdrr\brdrnil \gaph\cellx8640
\pard\intbl\itap1\pardeftab720\sl320\qr
\f0\fs24 \cf2 \cb3 1\
2\
3\
4\
5\
6\
7\
8\
9\
10\
11\
12\
13\
14\
15\
16\
17\
18\
19\
20\
21\
22\
23\
24\
25\
26\
27\
28\
29\
30\
31\
32\
33\
34\
35\
36\
37\
38\
39\
40\
41\
42\
43\
44\
45\
46\
47\
48\
49\
50\
51\
52\
53\
54\
55\
56\
57\
58\
59\
60\
61\
62\
63\
64\
65\
66\
67\
68\
69\
70\
71\
72\
73\
74\
75\
76\
77\
78\
79\
80\
81\
82\
83\
84\
85\
86\
87\
88\
89\
90\
91\
92\
93\
94\
95\
96\
97\cell
\pard\intbl\itap1\pardeftab720\sl320\ql\qnatural
\f1\i \cf5 \cb6 /*
\f0\i0 \cf4 \
\f1\i \cf5 532 - Dungeon Master
\f0\i0 \cf4 \
\f1\i \cf5 Randall Head
\f0\i0 \cf4 \
\f1\i \cf5 */
\f0\i0 \cf4 \
\pard\intbl\itap1\pardeftab720\sl320\ql\qnatural
\f2\b \cf7 #include <algorithm>
\f0\b0 \cf4 \
\f2\b \cf7 #include <iostream>
\f0\b0 \cf4 \
\f2\b \cf7 #include <iterator>
\f0\b0 \cf4 \
\f2\b \cf7 #include <numeric>
\f0\b0 \cf4 \
\f2\b \cf7 #include <sstream>
\f0\b0 \cf4 \
\f2\b \cf7 #include <fstream>
\f0\b0 \cf4 \
\f2\b \cf7 #include <cassert>
\f0\b0 \cf4 \
\f2\b \cf7 #include <climits>
\f0\b0 \cf4 \
\f2\b \cf7 #include <cstdlib>
\f0\b0 \cf4 \
\f2\b \cf7 #include <cstring>
\f0\b0 \cf4 \
\f2\b \cf7 #include <string>
\f0\b0 \cf4 \
\f2\b \cf7 #include <cstdio>
\f0\b0 \cf4 \
\f2\b \cf7 #include <vector>
\f0\b0 \cf4 \
\f2\b \cf7 #include <cmath>
\f0\b0 \cf4 \
\f2\b \cf7 #include <queue>
\f0\b0 \cf4 \
\f2\b \cf7 #include <deque>
\f0\b0 \cf4 \
\f2\b \cf7 #include <stack>
\f0\b0 \cf4 \
\f2\b \cf7 #include <list>
\f0\b0 \cf4 \
\f2\b \cf7 #include <map>
\f0\b0 \cf4 \
\f2\b \cf7 #include <set>
\f0\b0 \cf4 \
\pard\intbl\itap1\pardeftab720\sl320\ql\qnatural
\f2\b \cf4 using
\f0\b0
\f2\b namespace
\f0\b0 std;\
\
\pard\intbl\itap1\pardeftab720\sl320\ql\qnatural
\f2\b \cf8 int
\f0\b0 \cf4 positionsX[\cf9 6\cf4 ]
\f2\b =
\f0\b0 \{\cf9 0\cf4 ,\cf9 0\cf4 ,\cf9 0\cf4 ,
\f2\b -
\f0\b0 \cf9 1\cf4 ,\cf9 0\cf4 ,\cf9 1\cf4 \};\
\f2\b \cf8 int
\f0\b0 \cf4 positionsY[\cf9 6\cf4 ]
\f2\b =
\f0\b0 \{\cf9 0\cf4 ,\cf9 0\cf4 ,
\f2\b -
\f0\b0 \cf9 1\cf4 ,\cf9 0\cf4 ,\cf9 1\cf4 ,\cf9 0\cf4 \};\
\f2\b \cf8 int
\f0\b0 \cf4 positionsL[\cf9 6\cf4 ]
\f2\b =
\f0\b0 \{\cf9 1\cf4 ,
\f2\b -
\f0\b0 \cf9 1\cf4 ,\cf9 0\cf4 ,\cf9 0\cf4 ,\cf9 0\cf4 ,\cf9 0\cf4 \};\
\
\pard\intbl\itap1\pardeftab720\sl320\ql\qnatural
\f2\b \cf4 typedef
\f0\b0
\f2\b struct
\f0\b0 edge\{\
\'a0\'a0
\f2\b \cf8 int
\f0\b0 \cf4 l,r,c;\
\}edge;\
\
\pard\intbl\itap1\pardeftab720\sl320\ql\qnatural
\f2\b \cf8 int
\f0\b0 \cf4 L,R,C;\
\f2\b \cf8 int
\f0\b0 \cf4 visited[\cf9 30\cf4 ][\cf9 30\cf4 ][\cf9 30\cf4 ];\
\
\f2\b \cf8 bool
\f0\b0 \cf4
\f2\b \cf10 validPosition
\f0\b0 \cf4 (
\f2\b \cf8 int
\f0\b0 \cf4 l,
\f2\b \cf8 int
\f0\b0 \cf4 r,
\f2\b \cf8 int
\f0\b0 \cf4 c, vector
\f2\b <
\f0\b0 vector
\f2\b <
\f0\b0 vector
\f2\b <\cf8 char\cf4 >
\f0\b0
\f2\b >
\f0\b0
\f2\b >
\f0\b0
\f2\b *
\f0\b0 graph)\{\
\'a0\'a0\'a0\'a0
\f2\b if
\f0\b0 ((l
\f2\b <
\f0\b0 L
\f2\b &&
\f0\b0 l
\f2\b >=
\f0\b0 \cf9 0\cf4 )
\f2\b &&
\f0\b0 (r
\f2\b <
\f0\b0 R
\f2\b &&
\f0\b0 r
\f2\b >=
\f0\b0 \cf9 0\cf4 )
\f2\b &&
\f0\b0 (c
\f2\b <
\f0\b0 C
\f2\b &&
\f0\b0 c
\f2\b >=
\f0\b0 \cf9 0\cf4 ))\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b return
\f0\b0 (graph
\f2\b ->
\f0\b0 at(l)[r][c]
\f2\b ==
\f0\b0 \cf11 '.'
\f2\b \cf4 ||
\f0\b0 graph
\f2\b ->
\f0\b0 at(l)[r][c]
\f2\b ==
\f0\b0 \cf11 'E'\cf4 )
\f2\b ?
\f0\b0 \cf12 true
\f2\b \cf4 :
\f0\b0 \cf12 false\cf4 ;\
\'a0\'a0\'a0\'a0
\f2\b else
\f0\b0 \
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b return
\f0\b0 \cf12 false\cf4 ; \
\}\
\
\f2\b \cf8 int
\f0\b0 \cf4
\f2\b \cf10 bfs
\f0\b0 \cf4 (edge start, edge end, vector
\f2\b <
\f0\b0 vector
\f2\b <
\f0\b0 vector
\f2\b <\cf8 char\cf4 >
\f0\b0
\f2\b >
\f0\b0
\f2\b >
\f0\b0
\f2\b *
\f0\b0 graph)\{\
\'a0\'a0\'a0\'a0queue
\f2\b <
\f0\b0 edge
\f2\b >
\f0\b0 s;\
\'a0\'a0\'a0\'a0s.push(start);\
\'a0\'a0\'a0\'a0visited[start.l][start.r][start.c]
\f2\b =
\f0\b0 \cf9 0\cf4 ;\
\'a0\'a0\'a0\'a0
\f2\b while
\f0\b0 (s.empty()
\f2\b ==
\f0\b0 \cf12 false\cf4 ) \{\
\'a0\'a0\'a0\'a0\'a0\'a0edge top
\f2\b =
\f0\b0 s.front();\
\'a0\'a0\'a0\'a0\'a0\'a0s.pop();\
\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b if
\f0\b0 (end.l
\f2\b ==
\f0\b0 top.l
\f2\b &&
\f0\b0 end.r
\f2\b ==
\f0\b0 top.r
\f2\b &&
\f0\b0 end.c
\f2\b ==
\f0\b0 top.c)\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b return
\f0\b0 visited[top.l][top.r][top.c];\
\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b for
\f0\b0 (
\f2\b \cf8 int
\f0\b0 \cf4 i
\f2\b =
\f0\b0 \cf9 0\cf4 ; i
\f2\b <
\f0\b0 \cf9 6\cf4 ;
\f2\b ++
\f0\b0 i)\{\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b \cf8 int
\f0\b0 \cf4 newl
\f2\b =
\f0\b0 top.l
\f2\b +
\f0\b0 positionsL[i],newr
\f2\b =
\f0\b0 top.r
\f2\b +
\f0\b0 positionsX[i],newc
\f2\b =
\f0\b0 top.c
\f2\b +
\f0\b0 positionsY[i];\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b if
\f0\b0 (validPosition(newl,newr,newc,graph))\{\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b if
\f0\b0 (visited[newl][newr][newc]
\f2\b ==-
\f0\b0 \cf9 1\cf4 )\{\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0visited[newl][newr][newc]
\f2\b =
\f0\b0 visited[top.l][top.r][top.c]
\f2\b +
\f0\b0 \cf9 1\cf4 ;\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0edge node
\f2\b =
\f0\b0 \{newl,newr,newc\};\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0s.push(node);\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\}\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\}\
\'a0\'a0\'a0\'a0\'a0\'a0\}\
\'a0\'a0\'a0\'a0\}\
\'a0\'a0\'a0\'a0
\f2\b return
\f0\b0
\f2\b -
\f0\b0 \cf9 1\cf4 ;\
\}\
\
\f2\b \cf8 int
\f0\b0 \cf4
\f2\b \cf10 main
\f0\b0 \cf4 ()\{\
\'a0\'a0
\f2\b \cf8 char
\f0\b0 \cf4 po;\
\'a0\'a0edge start,end;\
\'a0\'a0
\f2\b while
\f0\b0 (scanf(\cf11 "%d %d %d"\cf4 ,
\f2\b &
\f0\b0 L,
\f2\b &
\f0\b0 R,
\f2\b &
\f0\b0 C)
\f2\b &&
\f0\b0 L
\f2\b &&
\f0\b0 R
\f2\b &&
\f0\b0 C)\{\
\'a0\'a0\'a0\'a0
\f1\i \cf5 //Reading the Graph :)
\f0\i0 \cf4 \
\'a0\'a0\'a0\'a0\'a0\'a0memset (visited,
\f2\b -
\f0\b0 \cf9 1\cf4 ,
\f2\b sizeof
\f0\b0 (visited));\
\'a0\'a0\'a0\'a0\'a0\'a0vector
\f2\b <
\f0\b0 vector
\f2\b <
\f0\b0 vector
\f2\b <\cf8 char\cf4 >
\f0\b0
\f2\b >
\f0\b0
\f2\b >
\f0\b0 graph;\
\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b for
\f0\b0 (
\f2\b \cf8 int
\f0\b0 \cf4 i
\f2\b =
\f0\b0 \cf9 0\cf4 ; i
\f2\b <
\f0\b0 L;
\f2\b ++
\f0\b0 i)\
\'a0\'a0\'a0\'a0\'a0\'a0\{ \
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0vector
\f2\b <
\f0\b0 vector
\f2\b <\cf8 char\cf4 >
\f0\b0
\f2\b >
\f0\b0 level;\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b for
\f0\b0 (
\f2\b \cf8 int
\f0\b0 \cf4 j
\f2\b =
\f0\b0 \cf9 0\cf4 ; j
\f2\b <
\f0\b0 R;
\f2\b ++
\f0\b0 j)\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\{\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0vector
\f2\b <\cf8 char\cf4 >
\f0\b0 row;\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b for
\f0\b0 (
\f2\b \cf8 int
\f0\b0 \cf4 k
\f2\b =
\f0\b0 \cf9 0\cf4 ; k
\f2\b <
\f0\b0 C;
\f2\b ++
\f0\b0 k)\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\{\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0cin
\f2\b >>
\f0\b0 po;\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b if
\f0\b0 (po
\f2\b ==
\f0\b0 \cf11 'S'\cf4 )\{start.l
\f2\b =
\f0\b0 i;start.r
\f2\b =
\f0\b0 j;start.c
\f2\b =
\f0\b0 k;\}\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b else
\f0\b0
\f2\b if
\f0\b0 (po
\f2\b ==
\f0\b0 \cf11 'E'\cf4 )\{end.l
\f2\b =
\f0\b0 i;end.r
\f2\b =
\f0\b0 j;end.c
\f2\b =
\f0\b0 k;\}\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0row.push_back(po);\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\}\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0level.push_back(row);\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0\}\
\'a0\'a0\'a0\'a0\'a0\'a0\'a0\'a0graph.push_back(level);\
\'a0\'a0\'a0\'a0\'a0\'a0\}\
\'a0\'a0\'a0\'a0\'a0\'a0
\f2\b \cf8 int
\f0\b0 \cf4 result
\f2\b =
\f0\b0 bfs(start,end,
\f2\b &
\f0\b0 graph);\
\'a0\'a0\'a0\'a0\'a0\'a0(result
\f2\b ==
\f0\b0
\f2\b -
\f0\b0 \cf9 1\cf4 )
\f2\b ?
\f0\b0 printf(\cf11 "Trapped!\\n"\cf4 )
\f2\b :
\f0\b0 printf(\cf11 "Escaped in %d minute(s).\\n"\cf4 ,result);\
\'a0\'a0\}\
\'a0\'a0
\f2\b return
\f0\b0 \cf9 0\cf4 ;\
\}\cell \lastrow\row
}
The statements and opinions included in these pages are those of only. Any statements and
opinions included in these pages are not those of Louisiana
State University or the LSU Board of Supervisors.
© 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015