CCF系列之I’m stuck!(201312-5)

  1 package ccf_text2013_12;
  2 
  3 import java.util.*;
  4 /**
  5  * I‘m stuck!
  6  * 　　给定一个R行C列的地图，地图的每一个方格可能是‘#‘, ‘+‘, ‘-‘, ‘|‘, ‘.‘, ‘S‘, ‘T‘七个字符中的一个，分别表示如下意思：
  7 　　‘#‘: 任何时候玩家都不能移动到此方格；
  8 　　‘+‘: 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非‘#‘方格移动一格；
  9 　　‘-‘: 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非‘#‘方格移动一格；
 10 　　‘|‘: 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非‘#‘方格移动一格；
 11 　　‘.‘: 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为‘#‘，则玩家不能再移动；
 12 　　‘S‘: 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非‘#‘方格移动一格；
 13 　　‘T‘: 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非‘#‘方格移动一格。
 14 　　此外，玩家不能移动出地图。
 15 　　请找出满足下面两个性质的方格个数：
 16 　　1. 玩家可以从初始位置移动到此方格；
 17 　　2. 玩家不可以从此方格移动到目标位置。
 18  * @author Hello stranger
 19  *
 20  */
 21 public class ImStuck {
 22     public static void main(String[] args) {
 23         new ImStuck().run();
 24     }
 25 
 26     public void run() {
 27         Scanner fin = new Scanner(System.in);
 28         int R = fin.nextInt();
 29         int C = fin.nextInt();
 30         fin.nextLine();
 31         int[][] board = new int[R + 2][C + 2];
 32         int rowStart = 0, colStart = 0, rowEnd = 0, colEnd = 0;
 33         for (int i = 1; i <= R; ++i) {
 34             String line = fin.nextLine();
 35             for (int j = 1; j <= C; ++j) {
 36                 char c = line.charAt(j - 1);
 37                 switch (c) {
 38                 case ‘#‘:
 39                     break;
 40                 case ‘-‘:
 41                     board[i][j] = 5;
 42                     break;
 43                 case ‘|‘:
 44                     board[i][j] = 0xA;
 45                     break;
 46                 case ‘+‘:
 47                 case ‘S‘:
 48                 case ‘T‘:
 49                     board[i][j] = 0xF;
 50                     break;
 51                 case ‘.‘:
 52                     board[i][j] = 0x8;
 53                     break;
 54                 default:
 55                     break;
 56                 }
 57                 if (c == ‘S‘) {
 58                     rowStart = i;
 59                     colStart = j;
 60                 } else if (c == ‘T‘) {
 61                     rowEnd = i;
 62                     colEnd = j;
 63                 }
 64             }
 65         }
 66         int[] dr = new int[] { 0, -1, 0, 1 };
 67         int[] dc = new int[] { 1, 0, -1, 0 };
 68         // Scan 1: find all cells which can reach T
 69         boolean[][] visited = new boolean[R + 2][C + 2];
 70         boolean[][] canReachT = new boolean[R + 2][C + 2];
 71         initVisited(visited);
 72         canReachT[rowEnd][colEnd] = true;
 73         visited[rowEnd][colEnd] = true;
 74         Queue<Integer> queue = new LinkedList<Integer>();
 75         queue.add(rowEnd);
 76         queue.add(colEnd);
 77         while (!queue.isEmpty()) {
 78             int r = queue.remove();
 79             int c = queue.remove();
 80             for (int i = 0; i < 4; ++i) {
 81                 int nr = r + dr[i];
 82                 int nc = c + dc[i];
 83                 if (visited[nr][nc])
 84                     continue;
 85                 if ((board[nr][nc] & (1 << ((i + 2) % 4))) != 0) {
 86                     canReachT[nr][nc] = true;
 87                     queue.add(nr);
 88                     queue.add(nc);
 89                     visited[nr][nc] = true;
 90                 }
 91             }
 92         }
 93         /*
 94          * for (int i = 1; i <= R; ++i) { for (int j = 1; j <= C; ++j) { if
 95          * (canReachT[i][j]) { System.out.println("i = " + i + ", j = " + j); }
 96          * } }
 97          */
 98         if (!canReachT[rowStart][colStart]) {
 99             System.out.println("I‘m stuck!");
100             return;
101         }
102         // Scan 2: get result
103         boolean[][] rCanReach = new boolean[R + 2][C + 2];
104         initVisited(visited);
105         queue.clear();
106         visited[rowStart][colStart] = true;
107         rCanReach[rowStart][colStart] = true;
108         queue.add(rowStart);
109         queue.add(colStart);
110         while (!queue.isEmpty()) {
111             int r = queue.remove();
112             int c = queue.remove();
113             for (int i = 0; i < 4; ++i) {
114                 if ((board[r][c] & (1 << i)) == 0)
115                     continue;
116                 int nr = r + dr[i];
117                 int nc = c + dc[i];
118                 if (visited[nr][nc])
119                     continue;
120                 if (board[nr][nc] == 0)
121                     continue;
122                 rCanReach[nr][nc] = true;
123                 queue.add(nr);
124                 queue.add(nc);
125                 visited[nr][nc] = true;
126             }
127         }
128         int result = 0;
129         for (int i = 1; i <= R; ++i) {
130             for (int j = 1; j <= C; ++j) {
131                 /*
132                  * if (rCanReach[i][j]) { System.out.println("i = " + i +
133                  * ", j = " + j); }
134                  */
135                 if (rCanReach[i][j] && (!canReachT[i][j]))
136                     ++result;
137             }
138         }
139         System.out.println(result);
140     }
141 
142     private void initVisited(boolean[][] visited) {
143         int R = visited.length - 2;
144         int C = visited[0].length - 2;
145         for (int i = 0; i <= R + 1; ++i) {
146             visited[i][0] = true;
147             visited[i][C + 1] = true;
148         }
149         for (int j = 0; j <= C + 1; ++j) {
150             visited[0][j] = true;
151             visited[R + 1][j] = true;
152         }
153         for (int i = 1; i <= R; ++i) {
154             for (int j = 1; j <= C; ++j) {
155                 visited[i][j] = false;
156 
157             }
158 
159         }
160 
161     }
162 }