[ Google CT2004 ] RoundA : Problem D. Cross the maze

Problem: 
Edison, a robot, does not have a right hand or eyes. As a brave robot, he always puts his left hand on the wall no matter he walks or turns around. Because he thinks it is too dangerous, Edison does not walk backward. 

Assume that Edison has found himself in a square-shaped maze of NxN square cells which is surrounded by walls from the outside. In the maze, some of the cells are also walls. Edison can only move between two empty cells in four directions, north, south, west and east. In order to get out of the maze, he drafts a plan. He uses his left hand to lean on the wall and goes by following the wall. 

Here is the question, is Edison able to get out of the maze in at most 10,000 steps? If he can make it, output the path. By getting out of the maze, he only needs to be in the exit cell. If the starting cell is the same as the exit, Edison won't need to move and can directly get out of the maze. 

Input: 
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with an integer N. N is the size of the maze. The following N lines, each line contains N characters which may be '.' or '#'. '.' is an empty cell, '#' is a wall. Followed by a line which contains four integers: sx, sy, ex, ey. (sx, sy) means that Edison is standing on row sx and column sy as his starting cell, (ex, ey) is the exit of the maze. (sx, sy) is guaranteed to be at one of the 4 corners of the maze, and Edison can only touch the wall on 4 adjacent cells(not 8) initially. (ex, ey) can be anywhere in the maze. Note that the top-left corner is at position (1,1). 

Output: 
For each test case, output a line containing "Case #x: y", where x is the case number (starting from 1) and y is "Edison ran out of energy." (without the quotes) if Edison can't reach the exit of the maze in at most 10,000 steps, otherwise y should be the number of steps followed by another line which contains y characters to describe the path (each character should be E for east, S for south, W for west or N for north). There is no character to represent the turning around. We don't care about the turning around steps, please only output the path of how Edison will cross the maze. 

Limits: 
1 ≤ T ≤ 30. 
1 ≤ sx, sy, ex, ey ≤ N. 
The starting cell and the exit of the maze will always be an empty cell. And the starting cell and the exit of the maze won't be the same. 
Small dataset 
2 ≤ N ≤ 10. 

Large dataset 
2 ≤ N ≤ 100. 

Sample: 

Input 
3
2
.#
#.
1 1 2 2
5
.##.#
.....
...#.
.###.
...#.
1 1 5 3
3
...
.#.
...
1 1 3 3

Output 
Case #1: Edison ran out of energy.
Case #2: 22
SEEENSESSSNNNWWSWWSSEE
Case #3: 4
EESS

One Solution: 
乍看是一個 Maze 的問題, 但多了一些限制: 

- 再走迷宮的時候左邊一定要有牆.
- 只能往前走, 不能往後走.
- 步數在 10,000 以內須能走到終點.

在這邊我們使用數字來定義方向: East=0; South=1; West=2; North=3 
 

在這個 Solution 我定義一個類別 Maze 來處理這個問題; 並使用類別 Point 來代表座標. 而該類別定義如下: 

view plaincopy to clipboardprint?

1. public static class Point{  
2.     // Note that the top-left corner is at position (1,1).   
3.     public int x;  
4.     public int y;  
5.       
6.     public Point(int x, int y){this.x = x; this.y = y;}  
7.       
8.     /** 
9.      * BD: The east coordination of current Point.  
10.      * @return 
11.      */  
12.     public Tuple east() {return new Tuple(x,y+1);}  
13.     public Tuple west() {return new Tuple(x,y-1);}  
14.     public Tuple south() {return new Tuple(x+1,y);}  
15.     public Tuple north() {return new Tuple(x-1,y);}  
16.       
17.     /** 
18.      * BD: Translate into coordination tuple. 
19.      * @param dir: Direction(0-3) 
20.      * @return Coordination Tuple(x,y) 
21.      */  
22.     public Tuple dir(int dir)  
23.     {  
24.         switch(dir)  
25.         {  
26.         case 0: // east  
27.             return east();                
28.         case 1: // south  
29.             return south();  
30.         case 2: // west  
31.             return west();  
32.         case 3: // north  
33.             return north();  
34.         }  
35.         return null;  
36.     }  
37.       
38.     /** 
39.      * BD: Given left hand direction and output face direction.  
40.      *     Ex. If you left hand is in east, it means you face south. 
41.      * @param lhdir: Left hand direction(0-3) 
42.      * @return Coordination Tuple(x,y) 
43.      */  
44.     public Tuple face(int lhdir)  
45.     {  
46.         switch(lhdir)  
47.         {  
48.         case 0: // east->south  
49.             return south();               
50.         case 1: // south  
51.             return west();  
52.         case 2: // west  
53.             return north();  
54.         case 3: // north  
55.             return east();  
56.         }  
57.         return null;  
58.     }  
59.       
60.     /** 
61.      * BD: Move according to given direction. 
62.      * @param dir: Direction to move 
63.      * @return Point after moving. 
64.      */  
65.     public Point move(int dir)  
66.     {  
67.         switch(dir)  
68.         {  
69.         case 0: // east  
70.             //System.out.printf("\t\tMove E\n");  
71.             return new Point(x,y+1);                  
72.         case 1: // south  
73.             //System.out.printf("\t\tMove S\n");  
74.             return new Point(x+1,y);  
75.         case 2: // west  
76.             //System.out.printf("\t\tMove W\n");  
77.             return new Point(x,y-1);  
78.         case 3: // north  
79.             //System.out.printf("\t\tMove N\n");  
80.             return new Point(x-1,y);  
81.         }  
82.         return null;  
83.     }                 
84.       
85.     @Override  
86.     public boolean equals(Object o)  
87.     {  
88.         if(o instanceof Point)  
89.         {  
90.             Point p = (Point)o;  
91.             if(p.x == x && p.y == y) return true;  
92.         }  
93.         return false;  
94.     }  
95.       
96.     @Override  
97.     public String toString(){return String.format("(%d,%d)", x,y);}  
98. }  

接著將圖形的長相輸入到 Maze 建構子後, 便可利用方法 go() 來走迷宮並輸出路徑的結果: 

view plaincopy to clipboardprint?

1. public static class Maze{  
2.     public Point start;  
3.     public Point end;         
4.     public List track;  
5.     public List move;  
6.     public int shape[][];  
7.     public int n;  
8.       
9.     public Maze(int n, List shapeList, int sx, int sy, int ex, int ey)  
10.     {  
11.         this.n = n;  
12.         start = new Point(sx, sy);  
13.         end = new Point(ex, ey);  
14.         shape = new int[n][n];  
15.         for(int x=0; x
16.         {  
17.             char[] yaxis = shapeList.get(x).toCharArray();  
18.             for(int y=0; y
19.             {  
20.                 if(yaxis[y]=='.') shape[x][y]= 0;  
21.                 else shape[x][y]= 1; // wall  
22.             }  
23.         }  
24.         track = new ArrayList();  
25.         move = new ArrayList();  
26.     }  
27.       
28.     /** 
29.      * BD: Check given coordination is wall or not. 
30.      * @param x: X axis 
31.      * @param y: Y axis 
32.      * @return True if the given coordination is wall; False otherwise. 
33.      */  
34.     public boolean isWall(int x, int y)  
35.     {  
36.         if(x<0 && x>=n) return true;  
37.         else if(y<0 && y>=n) return true;  
38.         else return shape[x][y]==1;  
39.     }  
40.       
41.     /** 
42.      * BD: Check given coordination is wall or not. 
43.      * @param t: Coordination tuple 
44.      * @return True if the given coordination is wall; False otherwise. 
45.      */  
46.     public boolean isWall(Tuple t)  
47.     {  
48.         int x = (Integer)t.get(0)-1;  
49.         int y = (Integer)t.get(1)-1;  
50.         if(x<0 || x>=n) return true;  
51.         else if(y<0 || y>=n) return true;  
52.         else {  
53.             //System.out.printf("\t[Test] n=%d; x=%d; y=%d\n", n ,x, y);  
54.             return shape[x][y]==1;  
55.         }  
56.     }  
57.       
58.     /** 
59.      * BD: Output one character to represent given direction(0-3) 
60.      * @param d: Direction(0-3) 
61.      * @return String to represent direction. 
62.      */  
63.     public String dir(int d)  
64.     {  
65.         switch(d)  
66.         {  
67.         case 0: // east  
68.             return "E";           
69.         case 1: // south  
70.             return "S";  
71.         case 2: // west  
72.             return "W";  
73.         case 3: // north  
74.             return "N";  
75.         }  
76.         return null;  
77.     }  
78.       
79.     /** 
80.      * BD: Return the direction after turning right. (E->S;S->W;W->N;N->E) 
81.      * @param dir: Current direction 
82.      * @return Direction after turning right. 
83.      */  
84.     public int turnRight(int dir) {return (dir+1)%4;}  
85.       
86.     /** 
87.      * BD: Return the direction after turning left. (E->N;N->E;E->S;S->E) 
88.      * @param dir: Current direction 
89.      * @return Direction after turning left. 
90.      */  
91.     public int turnLeft(int dir)  
92.     {  
93.         dir = dir-1;  
94.         if(dir<0) return dir+4;  
95.         return dir;  
96.     }  
97.       
98.     /** 
99.      * BD: Start running the maze. 
100.      * @return True if reaching destination; False otherwise. 
101.      * @throws Exception 
102.      */  
103.     public boolean go() throws Exception  
104.     {  
105.         int handDir=-1, moveDir=0;  
106.         track.add(start);  
107.         // Decide left hand direction  
108.         if(isWall(start.east())) handDir=0;  
109.         else if(isWall(start.south())) handDir=1;  
110.         else if(isWall(start.west())) handDir=2;  
111.         else if(isWall(start.north())) handDir=3;  
112.         System.out.printf("\t\tStart Left Hand Dir=%s %s:\n", dir(handDir), start);  
113.         int swd=0; // switch direction  
114.         for(int i=0; i<10000; i++)  
115.         {             
116.             Tuple ft = start.face(handDir);               
117.             if(isWall(ft))  
118.             {  
119.                 handDir=turnRight(handDir);  
120.                 //System.out.printf("\t\tChange Left Hand Dir=%s\n", dir(handDir));  
121.                 swd++;  
122.                 if(swd==4) return false;  
123.                 continue;  
124.             }  
125.             else swd=0;  
126.             moveDir = turnRight(handDir);  
127.             start = start.move(moveDir);  
128.             move.add(moveDir);  
129.             track.add(start);                                                             
130.             if(start.equals(end)) return true;  
131.             if(!isWall(start.dir(handDir))) // Turn around  
132.             {  
133.                 start = start.move(handDir);  
134.                 move.add(handDir);  
135.                 track.add(start);  
136.                 handDir = turnLeft(handDir);  
137.             }  
138.             if(start.equals(end)) return true;                
139.         }  
140.         return false;  
141.     }  
142.       
143.     public String trackStr()  
144.     {  
145.         StringBuffer strBuf = new StringBuffer();  
146.         for(int i:move) strBuf.append(dir(i));  
147.         return strBuf.toString();  
148.     }  
149.       
150.     @Override  
151.     public String toString()  
152.     {  
153.         StringBuffer strBuf = new StringBuffer();  
154.         for(int x=0; x
155.         {  
156.             for(int y=0; y
157.             {  
158.                 Point p = new Point(x+1,y+1);  
159.                 if(start.equals(p)) strBuf.append("S");  
160.                 else if(end.equals(p)) strBuf.append("E");  
161.                 else  
162.                 {  
163.                     if(shape[x][y]==0) strBuf.append(".");  
164.                     else strBuf.append("#");  
165.                 }  
166.             }  
167.             strBuf.append("\n");  
168.         }  
169.         return strBuf.toString();  
170.     }  
171. }  

而上面的 go() 方法即是走迷宮的演法算. 簡單來說有以下原則: 

0. 決定左手的方向 (左手必須有牆)
1. 如果面向的方向是牆的話, 則向右轉直到面向的方向沒有牆. (因為右轉後, 左手邊一定是牆)
1.1 如果連轉三次都是牆, 說明四面都是牆. 結束迷宮遊戲 (失敗).
2. 往前走一步 > start = start.move(moveDir); (start 紀錄目前所在的座標)
2.1 如果走完所在目標等於終點, 則結束迷宮遊戲 (成功).
2.2 如果目前左手邊不是牆則往左手邊移動 (因為左手邊一定要是牆), 並將左手的方向往左邊移動 > handDir = turnLeft(handDir)
2.3 如果走完所在目標等於終點, 則結束迷宮遊戲 (成功).
3. 重複 Step1, 2

而讀入輸入, 跑迷宮, 輸出結果代碼如下: 

view plaincopy to clipboardprint?

1. /** 
2. * BD: https://code.google.com/codejam/contest/2924486/dashboard#s=p3 
3. * @param args 
4. */  
5. public static void main(String[] args) throws Exception{  
6.     String fn="D-small-practice.in";  
7.     QSReader qsr = new QSReader(String.format("data/2014/%s", fn));  
8.     QSWriter qsw = new QSWriter(String.format("data/2014/%s.out", fn));  
9.     qsr.open();       
10.     Integer pc = Integer.valueOf(qsr.line());  
11.     System.out.printf("\t[Info] Total %d question...\n", pc);  
12.     for(int i=1; i<=pc; i++)  
13.     {  
14.         int n = Integer.valueOf(qsr.line());  
15.         List shape = new ArrayList();  
16.         for(int j=0; j// read maze  
17.         String pos[] = qsr.line().split(" "); // read start/end           
18.         Maze maze = new Maze(n, shape, Integer.valueOf(pos[0]), Integer.valueOf(pos[1]), Integer.valueOf(pos[2]), Integer.valueOf(pos[3]));  
19.         System.out.printf("\t\tP%d: Start(%s,%s), End(%s,%s)\n%s", i, pos[0],pos[1],pos[2],pos[3], maze);  
20.         if(maze.go())   
21.         {  
22.             String track = maze.trackStr();  
23.             qsw.line(String.format("Case #%d: %d\n%s", i, track.length(), track));  
24.         }  
25.         else  
26.         {  
27.             qsw.line(String.format("Case #%d: Edison ran out of energy.", i));  
28.         }  
29.     }  
30.       
31.     qsr.close();  
32.     qsw.close();  
33. }  

Supplement: 
* [ Algorithm ] Maze problem - Using Online DFS Search 
* [ Algorithm ] Maze problem - Using Online LRTA*