CCF 201312-5 I’m stuck!

問題描述

　　給定一個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
####.
           

樣例輸出

樣例說明

　　如果把滿足性質的方格在地圖上用’X’标記出來的話，地圖如下所示：

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

           

分析:

1、考查廣度優先搜尋

2、做了四小時才100分（自閉）

3、scanf("%c")可以讀入空格和換行符，要用cin.get()吸收換行符

我的代碼：

#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 55;
struct Node
{
	int x,y;
}S;
int R,C;
char mp[maxn][maxn];
int x[4] = {0,0,1,-1},y[4] = {1,-1,0,0};
vector<Node> v,vtemp; 
bool inq[maxn][maxn] = {false},flag = false;
bool judge(int x,int y)
{
	if (x < 0 || x >= R || y < 0 || y >= C) return false;
	if (mp[x][y] == '#' || inq[x][y] == true) return false;
	return true;	
}
void BFS(int x1,int y1)
{
	int left,right;
	queue<Node> q;
	S.x = x1,S.y = y1;
	q.push(S);
	inq[S.x][S.y] = true;
	while (!q.empty())
	{
		Node temp = q.front();
		q.pop();
		v.push_back(temp);
		if (mp[temp.x][temp.y] == 'T')
			flag = true;
		if (mp[temp.x][temp.y] == 'S' || mp[temp.x][temp.y] == 'T' || mp[temp.x][temp.y] == '+')
		{
			left = 0;
			right = 4;			
		}
		else if (mp[temp.x][temp.y] == '|')
		{
			left = 2;
			right = 4;			
		}
		else if (mp[temp.x][temp.y] == '-')
		{
			left = 0;
			right = 2;			
		}
		else if (mp[temp.x][temp.y] == '.')
		{
			left = 2;
			right = 3;			
		}
		for (int i = left ;i < right ;i++)
		{
			int newX = temp.x + x[i];
			int newY = temp.y + y[i];
			if (judge(newX,newY))
			{
				inq[newX][newY] = true;
				Node node;
				node.x = newX,node.y = newY;
				q.push(node);
			}
		}
	}
}
int main()
{
	scanf("%d%d",&R,&C);
	for (int i = 0 ;i < R ;i++)
	{
		cin.get();
		for (int j = 0 ;j < C ;j++)
		{
			scanf("%c",&mp[i][j]);
			if (mp[i][j] == 'S')
			{
				S.x = i;
				S.y = j;
			}
		}
	}
	int cnt = 0;
	BFS(S.x,S.y);
	if (flag == true)
	{
		vtemp = v;
		for (int i = 0 ;i < vtemp.size() ;i++)
		{
			fill(inq[0],inq[0] + maxn * maxn,false);
			flag = false;
			BFS(v[i].x,v[i].y);
			if (flag == false)
				cnt++;
		}
		printf("%d",cnt);
	}
	else
		printf("I'm stuck!");
	return 0;
}