201312-5 i'm stuck

Posted on | In |

问题描述

给定一个R行C列的地图，地图的每一个方格可能是’#’, ‘+’, ‘-‘, ‘|’, ‘.’, ‘S’, ‘T’七个字符中
的一个，分别表示如下意思：

‘#’: 任何时候玩家都不能移动到此方格；

‘+’: 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格；

‘-‘: 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非’#’方格移动一格；

‘|’: 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非’#’方格移动一格；

‘.’: 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为’#’，则玩家不能再移动；

‘S’: 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格；

‘T’: 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非’#’方格移动一格。

此外，玩家不能移动出地图。
　　请找出满足下面两个性质的方格个数：

  1. 玩家可以从初始位置移动到此方格；

  2. 玩家不可以从此方格移动到目标位置。

输入格式

输入的第一行包括两个整数R 和C，分别表示地图的行和列数。(1 ≤ R, C ≤ 50)。

接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个’S’和一个’T’。

输出格式

如果玩家在初始位置就已经不能到达终点了，就输出“I’m stuck!”（不含双引号）。否则的话，输出满足性质的方格的个数。
样例输入
5 5

–+-+

..|#.

..|##

S-+-T

####.

样例输出

2

样例说明

如果把满足性质的方格在地图上用’X’标记出来的话，地图如下所示：

–+-+

..|#X

..|##

S-+-T

####X

代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
#define MAX 100+10
struct direct{
	int rx,ry;
};
char grid[MAX][MAX];
int vis[MAX][MAX];
int vis2[MAX][MAX];
int r,c;
direct d[4]={{-1,0},{1,0},{0,-1},{0,1}};
bool isBound(int x,int l,int h){
	return x>=l&&x<=h;
}
bool isLegal(int x,int y){
	if(grid[x][y]!='#'&&!vis[x][y]&&isBound(x,0,r-1)&&isBound(y,0,c-1)){
		return true;
	}
	else return false;
}

void dfs(int x,int y){

	vis[x][y]=1;
	char t=grid[x][y];
	switch(t){
		case 'T':{
			for(int i=0;i<4;i++){
				int newx=x+d[i].rx,newy=y+d[i].ry;
				if(isLegal(newx,newy)) {
					//vis[newx][newy]=1;
					dfs(newx,newy);
				}
			}
			break;
		}
		case 'S':{
			for(int i=0;i<4;i++){
				int newx=x+d[i].rx,newy=y+d[i].ry;
				if(isLegal(newx,newy)) {
					//vis[newx][newy]=1;
					dfs(newx,newy);
				}
			}
			break;
		}
		case '+':{
			for(int i=0;i<4;i++){
				int newx=x+d[i].rx,newy=y+d[i].ry;
				if(isLegal(newx,newy)) {
					//vis[newx][newy]=1;
					dfs(newx,newy);
				}
			}
			break;
		}
			
		case '-':{
				for(int i=2;i<4;i++){
				int newx=x+d[i].rx,newy=y+d[i].ry;
				if(isLegal(newx,newy)) {
				//	vis[newx][newy]=1;
					dfs(newx,newy);
				}
			}
			break;
		}
		
		case '|':{
				for(int i=0;i<2;i++){
				int newx=x+d[i].rx,newy=y+d[i].ry;
				if(isLegal(newx,newy)) {
				////	vis[newx][newy]=1;
					dfs(newx,newy);
				}
			}
			break;
		}
		
		
		case '.':{
				int newx=x+d[1].rx,newy=y+d[1].ry;
				if(isLegal(newx,newy)) {
				//	vis[newx][newy]=1;
					dfs(newx,newy);
				}
			
			break;
		}
	}
	
}
int main(){
	cin>>r>>c;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			cin>>grid[i][j];
		}
	} 
	int sr,sc,er,ec;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			if(grid[i][j]=='S') {
			sr=i;sc=j;
			}
			if(grid[i][j]=='T')
			{
				er=i,ec=j;
			}
		}
		
	} 
	memset(vis,0,sizeof(vis));
	dfs(sr,sc);
	memcpy(vis2,vis,sizeof(vis));

	
	if(vis2[er][ec]==0) 
        cout << "I'm stuck!" << endl;
	else{
		int cnt=0;
		for(int i=0;i<r;i++){
			for(int j=0;j<c;j++){
				if(vis2[i][j]){
						memset(vis,0,sizeof(vis));//!!
					dfs(i,j);
					if(!vis[er][ec]) cnt++;
				}
			}
		
	}
		cout<<cnt<<endl;
	}
	
}