题目描述

有一个 N 行 M 列的二维表格，行的编号从上往下是 0 至 N-1,列的编号从左往右是 0 至M-1。每个格子是一个字符，其中‘.’表示可通行格子，‘#’表示障碍物格子。你的目标是从左上角格子(0,0)走到右下角格子(N-1,M-1)，每一步可以走到当前格子的上、下、左、右，4 个相邻的格子之一，但是不能走入障碍物格子。但是很遗憾，给你的二维表格保证，一开始你是无法完成目标的。对于某个障碍物格子，假如把该障碍物格子变成可通行格子，就能使得可以从左上角格子顺利走到右下角格子，那么该障碍物格子称为“善良障碍物格子”。你的任务是输出二维表格总共有多少个“善良障碍物格子”

输入格式

e.in
第一行，两个整数 N 和 M。2 <= N,M <= 100。
接下来是 N 行 M 列的二维表格。

输出格式

e.out
一个整数。

输入/输出例子1

输入：

4 6
..##..
..##..
...#..
..##..

输出：
1

代码

#include <iostream>
#include <queue>
using namespace std;
typedef struct{
    int x;
    int y;
}node;
queue<node> q;
int n,m,sum;
char map[105][105];
int vist[105][105];
char buff[105];
void acc(node no,int ox,int oy){
    if(oy>=1&&ox>=1&&ox<=n&&oy<=m){
        if(map[ox][oy]=='#'){
            if(vist[ox][oy]==0){
                vist[ox][oy]=no.x*m+no.y;
            }
            else if(vist[ox][oy]==no.x*m+no.y);
            else{
                sum++;
                vist[ox][oy]=no.x*m+no.y;
            }
        }
        else{
            if( vist[ox][oy]==0){
                vist[ox][oy]=1;
                node newNode={ox,oy};
                q.push(newNode);
            }
        }

    }
    
}
void bfs(node no){
    q.push(no);
    while (!q.empty()) {
        node ncur=q.front();
        q.pop();
        int ox,oy;
        //上
        ox=ncur.x;
        oy= ncur.y-1;
         acc(no,ox,oy);
        
        //下
        ox=ncur.x;
        oy=ncur.y+1;
        acc(no,ox,oy);
        
        //左
        ox=ncur.x-1;
        oy=ncur.y;
        acc(no,ox,oy);
        
        //右
        ox=ncur.x+1;
        oy=ncur.y;
        acc(no,ox,oy);
    }//end while
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>buff;
        for (int j=0;j<m;j++)
            map[i][j+1]=buff[j];
    }
    
    
    //求一能到达的#
    node n11={1,1};
    vist[1][1]=1;
    bfs(n11);
    node nmn={n,m};
    vist[n][m]=1;
    bfs(nmn);
    cout<<sum;
    return 0;
}