试题名称： I’m stuck!
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
问题描述
给定一个R行C列的地图，地图的每一个方格可能是'#', '+', '-', '|', '.', 'S', 'T'七个字符中的一个，分别表示如下意思：
'#': 任何时候玩家都不能移动到此方格；
'+': 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'-': 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非'#'方格移动一格；
'|': 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非'#'方格移动一格；
'.': 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为'#'，则玩家不能再移动；
'S': 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'T': 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格。
此外，玩家不能移动出地图。
请找出满足下面两个性质的方格个数：
1. 玩家可以从初始位置移动到此方格；
2. 玩家不可以从此方格移动到目标位置。
'#': 任何时候玩家都不能移动到此方格；
'+': 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'-': 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非'#'方格移动一格；
'|': 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非'#'方格移动一格；
'.': 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为'#'，则玩家不能再移动；
'S': 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'T': 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格。
此外，玩家不能移动出地图。
请找出满足下面两个性质的方格个数：
1. 玩家可以从初始位置移动到此方格；
2. 玩家不可以从此方格移动到目标位置。
输入格式
输入的第一行包括两个整数R 和C，分别表示地图的行和列数。(1 ≤ R, C ≤ 50)。
接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个'S'和一个'T'。
接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个'S'和一个'T'。
输出格式
如果玩家在初始位置就已经不能到达终点了，就输出“I'm stuck!”（不含双引号）。否则的话，输出满足性质的方格的个数。
样例输入
5 5
--+-+
..|#.
..|##
S-+-T
####.
--+-+
..|#.
..|##
S-+-T
####.
样例输出
2
样例说明
如果把满足性质的方格在地图上用'X'标记出来的话，地图如下所示：
--+-+
..|#X
..|##
S-+-T
####X
--+-+
..|#X
..|##
S-+-T
####X
解题思路:
1、深度遍历，选择队列。
2、方向和图形符号相互对应。
根据标准代码分析（java）：
package ccf_text2013_12; import java.util.*;
/**
* I'm stuck!
* 给定一个R行C列的地图，地图的每一个方格可能是'#', '+', '-', '|', '.', 'S', 'T'七个字符中的一个，分别表示如下意思：
'#': 任何时候玩家都不能移动到此方格；
'+': 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'-': 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非'#'方格移动一格；
'|': 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非'#'方格移动一格；
'.': 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为'#'，则玩家不能再移动；
'S': 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'T': 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格。
此外，玩家不能移动出地图。
请找出满足下面两个性质的方格个数：
1. 玩家可以从初始位置移动到此方格；
2. 玩家不可以从此方格移动到目标位置。
* @author Hello stranger
*
*/
public class ImStuck2 { public static void main(String[] args) { new ImStuck2().run();
} public void run() { Scanner fin = new Scanner(System.in); int R = fin.nextInt(); int C = fin.nextInt(); //判断图形的行和列 String first = fin.nextLine(); //跳过输入的换行（输入行列之后会打一个换行） //System.out.println(first); int[][] board = new int[R + 2][C + 2]; char[][] picture = new char[R][C]; //为了验证计算出的结果是否在图形上显示正确 int rowStart = 0, colStart = 0, rowEnd = 0, colEnd = 0; //起点和终点所在的行列 for (int i = 1; i <= R; ++i) { //读取输入的图形标志，并将图形标志转化为数字标示并保存在数组中,关键在于这些数字
/**
* # === 0
* - === 5
* | === 0xA == 10
* + === 0xF == 15
* S === 0xF == 15
* T === 0xF == 15
* . === 0x8 == 8
*
*/
String line = fin.nextLine(); for (int j = 1; j <= C; ++j) { char c = line.charAt(j - 1); picture[i-1][j-1] = c; switch (c) { case '#': break; case '-': board[i][j] = 5; break; case '|': board[i][j] = 0xA; break; case '+': case 'S': case 'T': board[i][j] = 0xF; break; case '.': board[i][j] = 0x8; break; default: break; }
if (c == 'S') { rowStart = i; colStart = j; //起点所在的行列 } else if (c == 'T') { rowEnd = i; colEnd = j; //终点所在的行列
}
}
}
System.out.println("用户输入的图形为：");
printCharArray(picture);
printNumArray(board);
int[] dr = new int[] { 0, -1, 0, 1 }; //行数 同行、上一行（向上）、 同行、 下一行（向下） int[] dc = new int[] { 1, 0, -1, 0 }; //列数 下一列（向右）、 同列、上一列（向左）、同列 // Scan 1: find all cells which can reach T boolean[][] visited = new boolean[R + 2][C + 2]; //默认均为false boolean[][] canReachT = new boolean[R + 2][C + 2]; //默认均为false initVisited(visited); //数组边框为true，中间为false canReachT[rowEnd][colEnd] = true; visited[rowEnd][colEnd] = true; //重点的值设为true Queue<Integer> queue = new LinkedList<Integer>(); queue.add(rowEnd); queue.add(colEnd); //队列有一个特点就是先进先出，这样就可以采用深度优先遍历 while (!queue.isEmpty()) { int r = queue.remove(); int c = queue.remove(); for (int i = 0; i < 4; ++i) { int nr = r + dr[i]; int nc = c + dc[i]; //判断顺序是 向右，向下，向左，向上(四个方向) if (visited[nr][nc]) //边框+已经判定可以到达终点的点 continue; if ((board[nr][nc] & (1 << ((i + 2) % 4))) != 0) { /**
* 方向 右 下 左 上
* i 0 1 2 3
* t = (i + 2) % 4 2 3 0 1
* x = 1 << t 4 8 1 2
* # === 0x0 == 0 & x 0 0 0 0
* - === 0x5 == 5 & x 4 0 1 0
* | === 0xA == 10 & x 0 8 0 2
* + === 0xF == 15 & x 4 8 1 2
* S === 0xF == 15 & x 4 8 1 2
* T === 0xF == 15 & x 4 8 1 2
* . === 0x8 == 8 & x 0 8 0 0
*
*/ //将上下左右和数字表示的图标对应起来，如果在这个方向可以走的话，就执行if语句 canReachT[nr][nc] = true; //这个数组里面值为false的即为玩家不可以从此方格移动到目标位置。 queue.add(nr); queue.add(nc); visited[nr][nc] = true;
}
}
} printBealoonArray(visited); if (!canReachT[rowStart][colStart]) { System.out.println("I'm stuck!"); return;
}
// Scan 2: get result 同理 boolean[][] rCanReach = new boolean[R + 2][C + 2]; initVisited(visited); queue.clear(); visited[rowStart][colStart] = true; rCanReach[rowStart][colStart] = true; queue.add(rowStart); queue.add(colStart); while (!queue.isEmpty()) { int r = queue.remove(); int c = queue.remove(); for (int i = 0; i < 4; ++i) { if ((board[r][c] & (1 << i)) == 0) continue; int nr = r + dr[i]; int nc = c + dc[i]; if (visited[nr][nc]) continue; if (board[nr][nc] == 0) continue; rCanReach[nr][nc] = true; //这个数组里面值为true的即为玩家可以从初始位置移动到此方格 queue.add(nr); queue.add(nc); visited[nr][nc] = true;
}
}
int result = 0; //符合两个条件的图所位于的行列 for (int i = 1; i <= R; ++i) { for (int j = 1; j <= C; ++j) { if (rCanReach[i][j] && (!canReachT[i][j])){ ++result; picture[i-1][j-1] = 'X'; } }
} System.out.println("经过计算之后的图形为："); printCharArray(picture); System.out.println("满足条件的位置有 " + result + " 个。");
} /**
* 预先初始化数组的时候多了边框，因为visited数组默认为false
* 此函数的目的是使得visited数组边框的默认值变为true
* 使得visited数组中间的值默认为false
* @param visited
*/ private void initVisited(boolean[][] visited) { int R = visited.length - 2; int C = visited[0].length - 2; for (int i = 0; i <= R + 1; ++i) { visited[i][0] = true; visited[i][C + 1] = true;
}
for (int j = 0; j <= C + 1; ++j) { visited[0][j] = true; visited[R + 1][j] = true;
}
for (int i = 1; i <= R; ++i) { for (int j = 1; j <= C; ++j) { visited[i][j] = false; } } }
/**
* 打印数组中保存的值
* 在此程序中为 输出等价于图形的数字数组
* @param queue
*/
public static void printNumArray(int[][] board){ System.out.println("=======================begin int board array====================="); for (int i = 0; i < board.length; ++i) { for (int j = 0; j < board[i].length; ++j) { System.out.print(board[i][j]+"\t");
}
System.out.println();
}
System.out.println("===========================end========================");
} /**
* 打印char数组中保存的值
* 在此程序中为 输出图形
* @param queue
*/
public static void printCharArray(char[][] picture){ System.out.println("=======================begin char picture array====================="); for (int i = 0; i < picture.length; ++i) { for (int j = 0; j < picture[i].length; ++j) { System.out.print(picture[i][j]);
}
System.out.println();
}
System.out.println("===========================end========================");
} /**
* 打印boolean数组中保存的值
* @param queue
*/
public static void printBealoonArray(boolean[][] visted){ System.out.println("=======================begin Boolean visted array ====================="); for (int i = 0; i < visted.length; ++i) { for (int j = 0; j < visted[i].length; ++j) { System.out.print(visted[i][j]+"\t");
}
System.out.println();
}
System.out.println("===========================end========================");
}
/**
* 打印队列中保存的值
* @param queue
*/
public static void printQueue(Queue<Integer> queue){ Iterator it = queue.iterator(); System.out.println("=======================begin queue====================="); int i = 0; while(it.hasNext()){ System.out.print(it.next() + "\t"); if((++i)%2 == 0){ System.out.println();
}
}
System.out.println("===========================end========================");
}
}
运行结果如下：
标准代码如下（java）：
package ccf_text2013_12; import java.util.*;
/**
* I'm stuck!
* 给定一个R行C列的地图，地图的每一个方格可能是'#', '+', '-', '|', '.', 'S', 'T'七个字符中的一个，分别表示如下意思：
'#': 任何时候玩家都不能移动到此方格；
'+': 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'-': 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非'#'方格移动一格；
'|': 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非'#'方格移动一格；
'.': 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为'#'，则玩家不能再移动；
'S': 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格；
'T': 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格。
此外，玩家不能移动出地图。
请找出满足下面两个性质的方格个数：
1. 玩家可以从初始位置移动到此方格；
2. 玩家不可以从此方格移动到目标位置。
* @author Hello stranger
*
*/
public class ImStuck {
public static void main(String[] args) {
new ImStuck().run();
} public void run() {
Scanner fin = new Scanner(System.in);
int R = fin.nextInt();
int C = fin.nextInt();
fin.nextLine();
int[][] board = new int[R + 2][C + 2];
int rowStart = 0, colStart = 0, rowEnd = 0, colEnd = 0;
for (int i = 1; i <= R; ++i) {
String line = fin.nextLine();
for (int j = 1; j <= C; ++j) {
char c = line.charAt(j - 1);
switch (c) {
case '#':
break;
case '-':
board[i][j] = 5;
break;
case '|':
board[i][j] = 0xA;
break;
case '+':
case 'S':
case 'T':
board[i][j] = 0xF;
break;
case '.':
board[i][j] = 0x8;
break;
default:
break;
}
if (c == 'S') {
rowStart = i;
colStart = j;
} else if (c == 'T') {
rowEnd = i;
colEnd = j;
}
}
}
int[] dr = new int[] { 0, -1, 0, 1 };
int[] dc = new int[] { 1, 0, -1, 0 };
// Scan 1: find all cells which can reach T
boolean[][] visited = new boolean[R + 2][C + 2];
boolean[][] canReachT = new boolean[R + 2][C + 2];
initVisited(visited);
canReachT[rowEnd][colEnd] = true;
visited[rowEnd][colEnd] = true;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(rowEnd);
queue.add(colEnd);
while (!queue.isEmpty()) {
int r = queue.remove();
int c = queue.remove();
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i];
int nc = c + dc[i];
if (visited[nr][nc])
continue;
if ((board[nr][nc] & (1 << ((i + 2) % 4))) != 0) {
canReachT[nr][nc] = true;
queue.add(nr);
queue.add(nc);
visited[nr][nc] = true;
}
}
}
/*
* for (int i = 1; i <= R; ++i) { for (int j = 1; j <= C; ++j) { if
* (canReachT[i][j]) { System.out.println("i = " + i + ", j = " + j); }
* } }
*/
if (!canReachT[rowStart][colStart]) {
System.out.println("I'm stuck!");
return;
}
// Scan 2: get result
boolean[][] rCanReach = new boolean[R + 2][C + 2];
initVisited(visited);
queue.clear();
visited[rowStart][colStart] = true;
rCanReach[rowStart][colStart] = true;
queue.add(rowStart);
queue.add(colStart);
while (!queue.isEmpty()) {
int r = queue.remove();
int c = queue.remove();
for (int i = 0; i < 4; ++i) {
if ((board[r][c] & (1 << i)) == 0)
continue;
int nr = r + dr[i];
int nc = c + dc[i];
if (visited[nr][nc])
continue;
if (board[nr][nc] == 0)
continue;
rCanReach[nr][nc] = true;
queue.add(nr);
queue.add(nc);
visited[nr][nc] = true;
}
}
int result = 0;
for (int i = 1; i <= R; ++i) {
for (int j = 1; j <= C; ++j) {
/*
* if (rCanReach[i][j]) { System.out.println("i = " + i +
* ", j = " + j); }
*/
if (rCanReach[i][j] && (!canReachT[i][j]))
++result;
}
}
System.out.println(result);
} private void initVisited(boolean[][] visited) {
int R = visited.length - 2;
int C = visited[0].length - 2;
for (int i = 0; i <= R + 1; ++i) {
visited[i][0] = true;
visited[i][C + 1] = true;
}
for (int j = 0; j <= C + 1; ++j) {
visited[0][j] = true;
visited[R + 1][j] = true;
}
for (int i = 1; i <= R; ++i) {
for (int j = 1; j <= C; ++j) {
visited[i][j] = false; } } }
}