天天看點

bfs-ccf-I’m stuck!

#include <iostream>

#include <stdio.h>

#include <queue>

#include <cstring>

using namespace std;

char mp[55][55];

int fp[55][55];

int tp[55][55];

int r,c,cot=0;

struct node

{

    int x,y;

};

int next[4][2]={{0,1},{0,-1},{-1,0},{1,0}};

void dfst(int x,int y)

{

    if(x>=r||x<0||y>=c||y<0)

        return ;

    if(mp[x][y]=='#'||tp[x][y]==1)

        return ;

    tp[x][y]=1 ;

    if(mp[x][y]=='+'||mp[x][y]=='S'||mp[x][y]=='T')

    for(int i=0;i<=3;i++)

        dfst(x+next[i][0],y+next[i][1]);

    if(mp[x][y]=='|')

    {

        dfst(x+1,y);

        dfst(x-1,y);

    }

    if(mp[x][y]=='-')

    {

        dfst(x,y+1);

        dfst(x,y-1);

    }

    if(mp[x][y]=='.')

        dfst(x+1,y);

}

void dfs(int x,int y)

{

    if(x>=r||x<0||y>=c||y<0)

        return ;

    if(mp[x][y]=='#'||fp[x][y]==1)

        return ;

    fp[x][y]=1;

    if(mp[x][y]=='+'||mp[x][y]=='S'||mp[x][y]=='T')

    for(int i=0;i<=3;i++)

        dfs(x+next[i][0],y+next[i][1]);

    if(mp[x][y]=='|')

    {

        dfs(x+1,y);

        dfs(x-1,y);

    }

    if(mp[x][y]=='-')

    {

        dfs(x,y+1);

        dfs(x,y-1);

    }

    if(mp[x][y]=='.')

        dfs(x+1,y);

}

int main()

{

    cin>>r>>c;

    int sx,sy,ex,ey;

    for(int i=0;i<r;i++)

      {

        scanf("%s",&mp[i]);

      }

    for(int i=0;i<r;i++)

        for(int j=0;j<c;j++)

        {

        if(mp[i][j]=='S')

            {

            sx=i;

            sy=j;

            }

        if(mp[i][j]=='T')

            {

            ex=i;

            ey=j;

            }

        }

    dfs(sx,sy);

    if(fp[ex][ey]==0)

        {

        printf("I'm stuck!\n");

        return 0;

        }

    for(int i=0;i<r;i++)

        for(int j=0;j<c;j++)

        {

        if(fp[i][j]==1)

        {

        memset(tp,0,sizeof(tp));

        dfst(i,j);

        if(tp[ex][ey]==0)

        cot++;

        }

        }

    printf("%d\n",cot);

    return 0;

}