试题编号： 201312-5¶
试题名称： I’m stuck!¶
时间限制： 1.0s¶
内存限制： 256.0MB¶
问题描述¶
原题链接: http://118.190.20.162/view.page?gpid=T1
给定一个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
题意¶
根据题意使用BFS模拟搜索过程即可。此题细节较多，值得注意。
思路¶
从S点开始搜索找到所有能到达的点。从所有能到达的点开始再进行搜索找到答案即可。
AC代码¶
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define ft first
#define sd second
#define pb push_back
const int maxn = 50 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
using namespace std;
char mmp[maxn][maxn];
int n,m;
bool vis[maxn][maxn],stk;
int walk[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct poi{
poi(int _x = 0,int _y = 0,char _val = 'a'):x(_x),y(_y),val(_val){}
int x,y;
char val;
}beg,ed;
bool check(int dx,int dy){
if(dx>=1 && dx<=n && dy>=1 && dy<=m && mmp[dx][dy]!= '#' && !vis[dx][dy])
return true;
else return false;
}
void bfs(poi beg){
queue<poi> ss;
ss.push(beg);
vis[beg.x][beg.y] = 1;
while(!ss.empty()){
poi temp = ss.front();ss.pop();
int dx = 0,dy = 0;
if(temp.val == 'S' || temp.val == '+' || temp.val == 'T'){
rep(i,0,3){
dx = temp.x + walk[i][0];
dy = temp.y + walk[i][1];
if(check(dx,dy)){
vis[dx][dy] = 1;
ss.push(poi(dx,dy,mmp[dx][dy]));
}
}
}else if(temp.val == '-'){
rep(i,2,3){
dx = temp.x;
dy = temp.y + walk[i][1];
if(check(dx,dy)){
vis[dx][dy] = 1;
ss.push(poi(dx,dy,mmp[dx][dy]));
}
}
}else if(temp.val == '.'){
dx = temp.x + 1;
dy = temp.y;
if(check(dx,dy)){
vis[dx][dy] = 1;
ss.push(poi(dx,dy,mmp[dx][dy]));
}
}else if(temp.val == '|'){
rep(i,0,1){
dx = temp.x + walk[i][0];
dy = temp.y;
if(check(dx,dy)){
vis[dx][dy] = 1;
ss.push(poi(dx,dy,mmp[dx][dy]));
}
}
}
}
}
bool bfs2(poi p){
queue<poi> ss;
ss.push(p);
while(!ss.empty()){
poi temp = ss.front();ss.pop();
if(temp.val == 'T'){
return false;
}
int dx = 0,dy = 0;
if(temp.val == 'S' || temp.val == '+' || temp.val == 'T'){
rep(i,0,3){
dx = temp.x + walk[i][0];
dy = temp.y + walk[i][1];
if(check(dx,dy)){
vis[dx][dy] = 1;
ss.push(poi(dx,dy,mmp[dx][dy]));
}
}
}else if(temp.val == '-'){
rep(i,2,3){
dx = temp.x;
dy = temp.y + walk[i][1];
if(check(dx,dy)){
vis[dx][dy] = 1;
ss.push(poi(dx,dy,mmp[dx][dy]));
}
}
}else if(temp.val == '.'){
dx = temp.x + 1;
dy = temp.y;
if(check(dx,dy)){
vis[dx][dy] = 1;
ss.push(poi(dx,dy,mmp[dx][dy]));
}
}else if(temp.val == '|'){
rep(i,0,1){
dx = temp.x + walk[i][0];
dy = temp.y;
if(check(dx,dy)){
vis[dx][dy] = 1;
ss.push(poi(dx,dy,mmp[dx][dy]));
}
}
}
}
return true;
}
int main() {
start;
cin>>n>>m;
rep(i,1,n){
rep(j,1,m){
cin>>mmp[i][j];
if(mmp[i][j] == 'S') beg = poi(i, j, mmp[i][j]);
else if(mmp[i][j] == 'T') ed = poi(i, j, mmp[i][j]);
}
}
bfs(beg);
/* rep(i,1,n){
rep(j,1,m){
if(vis[i][j]) cout<<mmp[i][j]<<' ';
else cout<<'#'<<' ';
}
cout<<endl;
}*/
if(!vis[ed.x][ed.y]) cout << "I'm stuck!\n";
else{
int cnt = 0;
queue<poi> t;
rep(i,1,n)
rep(j,1,m)
if(vis[i][j]) t.push(poi(i,j,mmp[i][j]));
while(!t.empty()){
poi tt = t.front();t.pop();
memset(vis,0,sizeof vis);
if(bfs2(tt)) cnt++;
}
cout<<cnt<<endl;
}
return 0;
}