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

——————————————————————————————————————————————————————————————————————

http://www.cnblogs.com/Ritchie/p/6141438.html

两次 DFS ，一次判断通否，并将走过的点标记，，一次从终点出发往回走，每次需要（逆着）判读前一点是否能到当前点

  1 #include<iostream>
  2 #include<vector>
  3 using namespace std;
  4 int vis[55][55]={0};
  5 
  6 int ans =0; 
  7 
  8 int R,C;
  9 
 10 //vector<vector<char> >v;                                  //    定义  大 小 
 11 
 12 char v[53][53]={0};
 13 
 14 int s_i,s_j,t_i,t_j;
 15 
 16 void dfs1(int i,int j)
 17 {
 18     if (vis[i][j]==1 || i<0 || i>=R || j<0 || j>=C || v[i][j]=='#')return ;
 19     
 20     vis[i][j] = 1;                    //                            不 用再置 为   0   ！！ 
 21     
 22     if (v[i][j]=='+')
 23     {
 24         dfs1(i-1,j);
 25         dfs1(i+1,j);
 26         dfs1(i,j+1);
 27         dfs1(i,j-1);
 28     }
 29     
 30     else if (v[i][j]=='-')
 31     {
 32         dfs1(i,j-1);
 33         dfs1(i,j+1);
 34     } 
 35     
 36     else if (v[i][j]=='|')
 37     {
 38         dfs1(i+1,j);
 39         dfs1(i-1,j);
 40     }
 41     
 42     else if (v[i][j]=='.')
 43     {
 44         dfs1(i+1,j);
 45     }
 46     
 47 }
 48 
 49 
 50 bool hefa(int i,int j)
 51 {
 52     if (i<0 || i>=R || j<0 || j>=C)return false;
 53     return true;
 54 }
 55 
 56 
 57 void dfs2(int i,int j)
 58 {
 59     if (  v[i][j]=='#' || vis[i][j]==2)return ;
 60 //if(v[i][j]=='#'||i<0||i>=R||j<0||j>=C||vis[i][j]==2) return;
 61     
 62     vis[i][j]=2;
 63     
 64 //    cout<<"--i,j "<<i<<" "<<j<<endl; 
 65     
 66     if ( hefa(i,j-1) && (v[i][j-1]=='-' || v[i][j-1]=='+'))
 67     {
 68         dfs2(i,j-1);
 69     }
 70     
 71     if (hefa(i,j+1) && (v[i][j+1]=='-' || v[i][j+1]=='+'))
 72     {
 73         dfs2(i,j+1);
 74     }
 75     
 76     if ( hefa(i+1,j) && (v[i+1][j]=='|' || v[i+1][j]=='+'))
 77     {
 78         dfs2(i+1,j);
 79      } 
 80      
 81      if ( hefa(i-1,j) && (v[i-1][j]=='.'|| v[i-1][j]=='+' || v[i-1][j]=='|'))
 82      {
 83          dfs2(i-1,j);
 84      }
 85     
 86     
 87 }
 88 
 89 int main()
 90 {
 91     
 92     cin>>R>>C;
 93 //    v.resize(R);
 94 //    for (int i=0;i<C;i++)v[i].resize(C);
 95     
 96     
 97     for (int i=0;i<R;i++)
 98     {
 99         for (int j =0;j<C;j++)
100         {
101             char s;
102             cin>>s;
103 
104             v[i][j]=s;
105             if (s=='S')
106             {
107                 s_i = i;
108                 s_j = j;
109                 v[i][j] = '+';
110             }
111             if (s=='T')
112             {
113                 t_i = i;
114                 t_j = j;
115                 v[i][j] = '+';
116             }
117         }
118     }
119     
120     dfs1(s_i,s_j);
121     
122 //    for (int i=0;i<R;i++)
123 //    {
124 //        for (int j=0;j<C;j++)cout<<vis[i][j]<<" ";         //cout<<v[i][j];     //cout<<vis[i][j]<<" ";
125 //        cout<<endl;
126 //    }
127     
128     
129     if (vis[t_i][t_j]==1)
130     {
131         dfs2(t_i,t_j);
132         for (int i=0;i<R;i++)
133         {
134             for (int j=0;j<C;j++)
135             {
136                 if (vis[i][j]==1)
137                 {
138 //                    cout<<"i,j "<<i<<" "<<j<<endl;
139                     ans++;
140                 }
141             }
142         }
143         cout<<ans<<endl;
144     }    
145     else cout<< "I'm stuck!"<<endl;
146     
147     return 0;
148  }