Advertisement
Guest User

Untitled

a guest
Apr 30th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. const int INF = 1000000000;
  10.  
  11. int getCellCode(int width, int cellRow, int cellColumn) {
  12. return cellRow * width + cellColumn;
  13. }
  14.  
  15. vector<vector<int> > buildConnectivityGraph(vector<string>& table) {
  16. vector<vector<int> > graph;
  17. if (table.empty()) {
  18. return graph;
  19. }
  20. int tableHeight = table.size(), tableWidth = table[0].length();
  21. graph.resize(tableHeight * tableWidth);
  22. for (int rowNumber = 0; rowNumber < tableHeight; ++rowNumber) {
  23. for (int columnNumber = 0; columnNumber < tableWidth; ++columnNumber) {
  24. if (table[rowNumber][columnNumber] == '*')
  25. continue;
  26. int cellCode = getCellCode(tableWidth, rowNumber, columnNumber);
  27. for (int adjacentCellColumn = columnNumber - 1; adjacentCellColumn >= 0; --adjacentCellColumn) {
  28. if (table[rowNumber][adjacentCellColumn] == '*')
  29. break;
  30. else {
  31. graph[cellCode].push_back(getCellCode(tableWidth, rowNumber, adjacentCellColumn));
  32. }
  33. }
  34. for (int adjacentCellColumn = columnNumber + 1; adjacentCellColumn < tableWidth; ++adjacentCellColumn) {
  35. if (table[rowNumber][adjacentCellColumn] == '*')
  36. break;
  37. else {
  38. graph[cellCode].push_back(getCellCode(tableWidth, rowNumber, adjacentCellColumn));
  39. }
  40. }
  41. for (int adjacentCellRow = rowNumber - 1; adjacentCellRow >= 0; --adjacentCellRow) {
  42. if (table[adjacentCellRow][columnNumber] == '*')
  43. break;
  44. else {
  45. graph[cellCode].push_back(getCellCode(tableWidth, adjacentCellRow, columnNumber));
  46. }
  47. }
  48. for (int adjacentCellRow = rowNumber + 1; adjacentCellRow < tableHeight; ++adjacentCellRow) {
  49. if (table[adjacentCellRow][columnNumber] == '*')
  50. break;
  51. else {
  52. graph[cellCode].push_back(getCellCode(tableWidth, adjacentCellRow, columnNumber));
  53. }
  54. }
  55. }
  56. }
  57. return graph;
  58. }
  59.  
  60. int main()
  61. {
  62. int width, height;
  63. cin >> width >> height;
  64. vector<string> table(height);
  65. for (int rowNumber = 0; rowNumber < height; ++rowNumber) {
  66. cin >> table[rowNumber];
  67. }
  68. int firstCowRow = -1, firstCowColumn = -1;
  69. int secondCowRow = -1, secondCowColumn = -1;
  70. for (int rowNumber = 0; rowNumber < height; ++rowNumber) {
  71. for (int columnNumber = 0; columnNumber < width; ++columnNumber) {
  72. if (table[rowNumber][columnNumber] == 'C') {
  73. if (firstCowRow == -1 && firstCowColumn == -1) {
  74. firstCowRow = rowNumber;
  75. firstCowColumn = columnNumber;
  76. }
  77. else {
  78. secondCowRow = rowNumber;
  79. secondCowColumn = columnNumber;
  80. }
  81. }
  82. }
  83. }
  84. vector<vector<int> > graph = buildConnectivityGraph(table);
  85. vector<int> distances(graph.size());
  86.  
  87. int startVertex = getCellCode(width, firstCowRow, firstCowColumn);
  88. int endVertex = getCellCode(width, secondCowRow, secondCowColumn);
  89. for (int vertexIterator = 0; vertexIterator < distances.size(); ++vertexIterator) {
  90. distances[vertexIterator] = INF;
  91. }
  92. distances[startVertex] = -1;
  93. queue<int> bfsQueue;
  94. bfsQueue.push(startVertex);
  95. while (!bfsQueue.empty()) {
  96. int currentVertex = bfsQueue.front();
  97. if (currentVertex == endVertex) {
  98. cout << distances[endVertex] << endl;
  99. return 0;
  100. }
  101. bfsQueue.pop();
  102. for (int adjacentVerticesIterator = 0; adjacentVerticesIterator < graph[currentVertex].size(); ++adjacentVerticesIterator) {
  103. if (distances[graph[currentVertex][adjacentVerticesIterator]] != INF)
  104. continue;
  105. distances[graph[currentVertex][adjacentVerticesIterator]] = distances[currentVertex] + 1;
  106. bfsQueue.push(graph[currentVertex][adjacentVerticesIterator]);
  107. }
  108. }
  109. return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement