Advertisement
Guest User

Untitled

a guest
Mar 27th, 2017
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. char tab[2000][2000];
  8.  
  9. void bfsCitiesSearch(int n, int m, int whichRow, int whichCol, int &count, int isStartingPoint)
  10. {
  11. if(whichRow >= n || whichCol >= m)
  12. return ;
  13. switch(tab[whichRow][whichCol])
  14. {
  15. case 'v':
  16. {
  17. if(whichRow + 1 == n && whichCol + 1 == m)
  18. return ;
  19. if(whichCol + 1 == m)
  20. bfsCitiesSearch(n, m, whichRow + 1, 0, count, 1);
  21. else
  22. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 1);
  23. }
  24. break;
  25.  
  26. case 'A':
  27. {
  28. if(whichRow + 1 == n && whichCol + 1 == m)
  29. return ;
  30. tab[whichRow][whichCol] = 'v';
  31. if(whichCol + 1 == m)
  32. bfsCitiesSearch(n, m, whichRow + 1, 0, count, 1);
  33. else
  34. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 1);
  35. }
  36. break;
  37.  
  38. case 'B':
  39. {
  40. tab[whichRow][whichCol] = 'v';
  41. if(isStartingPoint == 1)
  42. count++;
  43. if(whichCol - 1 >= 0)
  44. {
  45. char left = tab[whichRow][whichCol - 1];
  46. if(left == 'D' || left == 'E' || left == 'F')
  47. bfsCitiesSearch(n, m, whichRow, whichCol - 1, count, 0);
  48. }
  49. if(whichRow + 1 < n)
  50. {
  51. char down = tab[whichRow + 1][whichCol];
  52. if(down == 'C' || down == 'D' || down == 'F')
  53. bfsCitiesSearch(n, m, whichRow + 1, whichCol, count, 0);
  54. }
  55. if(whichCol + 1 == m && whichRow + 1 == n)
  56. return ;
  57. else
  58. {
  59. if(isStartingPoint == 1)
  60. {
  61. if(whichCol + 1 == m)
  62. bfsCitiesSearch(n, m, whichRow + 1, 0, count, 1);
  63. else
  64. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 1);
  65. }
  66. }
  67. }
  68. break;
  69.  
  70. case 'C':
  71. {
  72. tab[whichRow][whichCol] = 'v';
  73. if(isStartingPoint == 1)
  74. count++;
  75. if(whichCol - 1 >= 0)
  76. {
  77. char left = tab[whichRow][whichCol - 1];
  78. if(left == 'D' || left == 'E' || left == 'F')
  79. bfsCitiesSearch(n, m, whichRow, whichCol - 1, count, 0);
  80. }
  81.  
  82. if(whichRow - 1 >= 0)
  83. {
  84. char up = tab[whichRow - 1][whichCol];
  85. if(up == 'B' || up == 'E' || up == 'F')
  86. bfsCitiesSearch(n, m, whichRow - 1, whichCol, count, 0);
  87. }
  88. if(whichCol + 1 == m && whichRow + 1 == n)
  89. return ;
  90. else
  91. {
  92. if(isStartingPoint == 1)
  93. {
  94. if(whichCol + 1 == m)
  95. bfsCitiesSearch(n, m, whichRow + 1, 0, count, 1);
  96. else
  97. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 1);
  98. }
  99. }
  100.  
  101. }
  102. break;
  103.  
  104. case 'D':
  105. {
  106. tab[whichRow][whichCol] = 'v';
  107. if(isStartingPoint == 1)
  108. count++;
  109. if(whichCol + 1 < m)
  110. {
  111. char right = tab[whichRow][whichCol + 1];
  112. if(right == 'B' || right == 'C' || right == 'F')
  113. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 0);
  114. }
  115.  
  116. if(whichRow - 1 >= 0)
  117. {
  118. char up = tab[whichRow - 1][whichCol];
  119. if(up == 'B' || up == 'E' || up == 'F')
  120. bfsCitiesSearch(n, m, whichRow - 1, whichCol, count, 0);
  121. }
  122. if(whichCol + 1 == m && whichRow + 1 == n)
  123. return ;
  124. else
  125. {
  126. if(isStartingPoint == 1)
  127. {
  128. if(whichCol + 1 == m)
  129. bfsCitiesSearch(n, m, whichRow + 1, 0, count, 1);
  130. else
  131. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 1);
  132. }
  133.  
  134. }
  135. }
  136. break;
  137.  
  138. case 'E':
  139. {
  140. tab[whichRow][whichCol] = 'v';
  141. if(isStartingPoint == 1)
  142. count++;
  143. if(whichCol + 1 < m)
  144. {
  145. char right = tab[whichRow][whichCol + 1];
  146. if(right == 'B' || right == 'C' || right == 'F')
  147. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 0);
  148. }
  149. if(whichRow + 1 < n)
  150. {
  151. char down = tab[whichRow + 1][whichCol];
  152. if(down == 'C' || down == 'D' || down == 'F')
  153. bfsCitiesSearch(n, m, whichRow + 1, whichCol, count, 0);
  154. }
  155. if(whichCol + 1 == m && whichRow + 1 == n)
  156. return ;
  157. else
  158. {
  159. if(isStartingPoint == 1)
  160. {
  161. if(whichCol + 1 == m)
  162. bfsCitiesSearch(n, m, whichRow + 1, 0, count, 1);
  163. else
  164. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 1);
  165. }
  166. }
  167. }
  168. break;
  169.  
  170. case 'F':
  171. {
  172. tab[whichRow][whichCol] = 'v';
  173. if(isStartingPoint == 1)
  174. count++;
  175. if(whichCol + 1 < m)
  176. {
  177. char right = tab[whichRow][whichCol + 1];
  178. if(right == 'B' || right == 'C' || right == 'F')
  179. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 0);
  180. }
  181. if(whichRow + 1 < n)
  182. {
  183. char down = tab[whichRow + 1][whichCol];
  184. if(down == 'C' || down == 'D' || down == 'F')
  185. bfsCitiesSearch(n, m, whichRow + 1, whichCol, count, 0);
  186. }
  187. if(whichCol - 1 >= 0)
  188. {
  189. char left = tab[whichRow][whichCol - 1];
  190. if(left == 'D' || left == 'E' || left == 'F')
  191. bfsCitiesSearch(n, m, whichRow, whichCol - 1, count, 0);
  192. }
  193.  
  194. if(whichRow - 1 >= 0)
  195. {
  196. char up = tab[whichRow - 1][whichCol];
  197. if(up == 'B' || up == 'E' || up == 'F')
  198. bfsCitiesSearch(n, m, whichRow - 1, whichCol, count, 0);
  199. }
  200. if(whichCol + 1 == m && whichRow + 1 == n)
  201. return ;
  202. else
  203. {
  204. if(isStartingPoint == 1)
  205. {
  206. if(whichCol + 1 == m)
  207. bfsCitiesSearch(n, m, whichRow + 1, 0, count, 1);
  208. else
  209. bfsCitiesSearch(n, m, whichRow, whichCol + 1, count, 1);
  210. }
  211. }
  212.  
  213.  
  214. }
  215. break;
  216. }
  217. }
  218.  
  219.  
  220. int main()
  221. {
  222. int n,m; //rows and colums of a field
  223. int max = 2000;
  224. char text[max];
  225. char *line;
  226. line = fgets(text,max,stdin);
  227. sscanf(line,"%d %d",&n,&m);
  228. int i = 0; //to iterate over main loop
  229. int j = 0; //to iterate over tab
  230. int k = 0; //to iterate over line
  231.  
  232. //assigning values to an array
  233. while(i < n)
  234. {
  235. line = fgets(text,max,stdin);
  236. while(k < m)
  237. {
  238. tab[i][k] = line[k];
  239. k++;
  240. }
  241. k = 0;
  242. i++;
  243. }
  244.  
  245. int count = 0;
  246. bfsCitiesSearch(n, m, 0, 0, count, 1);
  247. printf("%d",count);
  248.  
  249.  
  250.  
  251.  
  252.  
  253. return 0;
  254. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement