2013_12_CSP_5

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;

struct pos//位置坐标
{
    int R;//行数
    int C;//列数
}tmp,tmp2;//临时坐标1,临时坐标2

int R, C;//地图的行数与列数
int S_R, S_C, T_R, T_C;//存储初始位置坐标与目标位置坐标
bool task1_use[50][50] = {false};//满足性质1即初始坐标能到达的点
bool task2_use[50][50] = {false};//探测能到达T点的点,性质2相反
char maps[50][50];//地图存储位置
queue<pos> queues;//坐标队列

bool bounds(int R_in, int C_in)//探测是否越界,若不越界输出true
{
    if((R_in >= 0)&&(R_in < R)&&(C_in >= 0)&&(C_in < C))
    {
        return true;
    }
    return false;
}

void task1_deal(int R_in, int C_in)
{
    //如果不越界且不为#且未抵达过则运行
    if(bounds(R_in, C_in)&&(maps[R_in][C_in] != '#')&&(!task1_use[R_in][C_in]))
    {
        task1_use[R_in][C_in] = true;//设置该点已抵达
        tmp.R = R_in, tmp.C = C_in;//临时变量存储坐标
        queues.push(tmp);//插入该坐标点
    }
}

bool BFS_S()//由S点开始遍历
{
    bool T_flag = false;
    while(!queues.empty()) queues.pop();//队列初始化
    tmp.R = S_R, tmp.C = S_C;//赋予临时变量S坐标
    queues.push(tmp);//S坐标进队列
    task1_use[tmp.R][tmp.C] = true;//标记初始坐标可到达

    while(!queues.empty())
    {
        tmp2 = queues.front();//获取队列头部坐标
        queues.pop();//弹出队列头部
        char c = maps[tmp2.R][tmp2.C];//读入对应字符
        if(c == 'T') T_flag = true;//已到达目标则设置flag为true
        if(c != '#')
        {
            if((c == 'S')||(c == 'T')||(c == '+'))
            {
                task1_deal(tmp2.R - 1, tmp2.C);//上
                task1_deal(tmp2.R + 1, tmp2.C);//下
                task1_deal(tmp2.R, tmp2.C - 1);//左
                task1_deal(tmp2.R, tmp2.C + 1);//右
            }
            else if(c == '-')
            {
                task1_deal(tmp2.R, tmp2.C - 1);//左
                task1_deal(tmp2.R, tmp2.C + 1);//右
            }
            else if(c == '|')
            {
                task1_deal(tmp2.R - 1, tmp2.C);//上
                task1_deal(tmp2.R + 1, tmp2.C);//下
            }
            else if(c == '.')
            {
                task1_deal(tmp2.R + 1, tmp2.C);//下
            }
        }
    }
    return T_flag;
}

//判断该点是否可以到达目标坐标,type:该点在上个点的方位,0上1下2左3右
void task2_deal(int R_in, int C_in, int type)
{
    tmp.R = R_in, tmp.C = C_in;//临时变量存储坐标
    //如果不越界且不为#且目前不能确定能否到达目标坐标则运行
    if(bounds(R_in, C_in)&&(maps[R_in][C_in]!='#')&&(!task2_use[R_in][C_in]))
    {
        char c = maps[R_in][C_in];//读入对应字符
        if((c == 'S')||(c == 'T')||(c == '+'))//若为此三者必能到达T点
        {
            task2_use[R_in][C_in] = true;
            queues.push(tmp);//插入该坐标点
        }
        else if(c == '-')
        {
            if((type == 2)||(type == 3))//左右
            {
                task2_use[R_in][C_in] = true;
                queues.push(tmp);//插入该坐标点
            }
        }
        else if(c == '|')
        {
            if((type == 0)||(type == 1))//上下
            {
                task2_use[R_in][C_in] = true;
                queues.push(tmp);//插入该坐标点
            }
        }
        else if(c == '.')
        {
            if(type == 0)//该点需在上个点的上方
            {
                task2_use[R_in][C_in] = true;
                queues.push(tmp);//插入该坐标点
            }
        }
    }
}


void BFS_T()//由T点开始遍历,探测能到达T点的点
{
    tmp.R = T_R, tmp.C = T_C;//赋予临时变量T坐标
    while(!queues.empty()) queues.pop();//队列初始化
    queues.push(tmp);//S坐标进队列
    task2_use[tmp.R][tmp.C] = true;//标记目标坐标即是T点,肯定可以到达T点
    while(!queues.empty())
    {
        tmp2 = queues.front();//获取队列头部坐标
        queues.pop();//弹出队列头部
        task2_deal(tmp2.R - 1, tmp2.C, 0);//上
        task2_deal(tmp2.R + 1, tmp2.C, 1);//下
        task2_deal(tmp2.R, tmp2.C - 1, 2);//左
        task2_deal(tmp2.R, tmp2.C + 1, 3);//右
    }
}

int main()
{
    cin >> R >> C;//读入地图的行数与列数
    for(int i = 0;i < R;i++)
    {
        for(int j = 0;j < C;j++)
        {
            cin >> maps[i][j];
            if(maps[i][j] == 'S') S_R = i,S_C = j;//导入S坐标
            if(maps[i][j] == 'T') T_R = i,T_C = j;//导入T坐标
        }
        getchar();
    }

    if(BFS_S())//寻找初始坐标是否到达目标点
    {
        BFS_T();//寻找目标可到达点
        int task_sum = 0;//满足性质1与2的点的个数
        for(int i = 0;i < R;i++)
        {
            for(int j = 0;j < C;j++)
            {
                if((task1_use[i][j])&&(!task2_use[i][j])) task_sum++;
                //满足任务1而不满足任务2的点就是要求的目标
            }
        }
        cout << task_sum << endl;//输出满足性质1与2的点的个数
    }
    else cout << "I'm stuck!" << endl;
    return 0;
}