2013年12月CCF计算机软件能力认证第五题 I’m stuck!(逆向dfs bfs）

glm233

发布于 2021-03-04 10:38:05

2280

发布于 2021-03-04 10:38:05

文章被收录于专栏：glm的全栈学习之路

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

#: 任何时候玩家都不能移动到此方格；
+: 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格；
-: 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非 # 方格移动一格；
|: 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非 # 方格移动一格；
.: 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为 #，则玩家不能再移动；
S: 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格；
T: 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非 # 方格移动一格。

此外，玩家不能移动出地图。

请找出满足下面两个性质的方格个数：

玩家可以从初始位置移动到此方格；
玩家不可以从此方格移动到目标位置。

输入格式

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

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

输出格式

如果玩家在初始位置就已经不能到达终点了，就输出 I'm stuck!。

否则的话，输出满足性质的方格的个数。

数据范围

1≤R,C≤50

输入样例：

5 5
--+-+
..|#.
..|##
S-+-T
####.

输出样例：

样例解释

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

--+-+
..|#X
..|##
S-+-T
####X

思路：其实这道题仔细分析是水的，因为题目要求如果初始位置不能到终点输出一句，那不就是初始位置正着做一次dfs/bfs能到就可以到喽不能到就直接输出

如果可以到，在思考，对初始位置做一次bfs/dfs，我们就可以求出地图上可以从初始位置到的点

那么不能从该方格到的点，其实我们需要从终点反着dfs/bfs就好，什么叫反着，就比如正常我们dfs的时候上下左右只要这个点能到就行，但是现在我们是从终点反着来，当然终点是上下左右都可以走，但是如果终点到了'.'这个位置，除非是向上走到的，否则不能从‘.’这个位置到终点好好理解一下这个话具体看下面代码

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int r,c,ans,stx,sty,edx,edy,vis[N][N];
char s[N][N];
bool ok1[N][N],ok2[N][N];
int dx[]={0,0,1,-1},dy[]={-1,1,0,0};
void dfs1(int x,int y){
    ok1[x][y]=1;
    vis[x][y]=1;
    int rel,rer;
    if(s[x][y]=='+'||s[x][y]=='S'||s[x][y]=='T')rel=0,rer=4;
    else if(s[x][y]=='-')rel=0,rer=2;
    else if(s[x][y]=='|')rel=2,rer=4;
    else if(s[x][y]=='.')rel=2,rer=3;
    //cout<<rel<<" "<<rer<<endl<<endl;
    for(int i=rel;i<rer;i++){
        int nx=x+dx[i],ny=y+dy[i];
        //cout<<nx<<" "<<ny<<endl;
        if(nx<0||nx>r-1||ny<0||ny>c-1||s[nx][ny]=='#'||vis[nx][ny])continue;
        dfs1(nx,ny);
    }
}
void dfs2(int x,int y){
    //cout<<x<<" "<<y<<" "<<s[x][y]<<endl;
    ok2[x][y]=1;
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        //cout<<nx<<" "<<ny<<endl;
        if(nx<0||nx>r-1||ny<0||ny>c-1||s[nx][ny]=='#'||vis[nx][ny])continue;
        if(s[nx][ny]=='+'||s[nx][ny]=='S'||s[nx][ny]=='T'){
            dfs2(nx,ny);
            continue;
        }
        if(s[nx][ny]=='-'&&(i==0||i==1)){
            dfs2(nx,ny);
            continue;
        }
        if(s[nx][ny]=='.'&&i==3){
            dfs2(nx,ny);
            continue;
        }
        if(s[nx][ny]=='|'&&(i==2||i==3)){
            dfs2(nx,ny);
            continue;
        }
    }
}
int main(){
    cin>>r>>c;
    for(int i=0;i<r;i++)cin>>s[i];
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(s[i][j]=='S'){
                stx=i,sty=j;
            }
            if(s[i][j]=='T'){
                edx=i,edy=j;
            }
        }
    }
    dfs1(stx,sty);
    memset(vis,0,sizeof vis);
    dfs2(edx,edy);
    if(!ok2[stx][sty]){
        cout<<"I'm stuck!"<<endl;
    }
    else{
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(ok1[i][j]&&!ok2[i][j])ans++;
            }
        }
        cout<<ans<<endl;
    }
    
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/02/25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

node.js

登录后参与评论

0 条评论

热度