Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <queue>
- using namespace std;
- const int INF = 1000000000;
- int getCellCode(int width, int cellRow, int cellColumn) {
- return cellRow * width + cellColumn;
- }
- vector<vector<int> > buildConnectivityGraph(vector<string>& table) {
- vector<vector<int> > graph;
- if (table.empty()) {
- return graph;
- }
- int tableHeight = table.size(), tableWidth = table[0].length();
- graph.resize(tableHeight * tableWidth);
- for (int rowNumber = 0; rowNumber < tableHeight; ++rowNumber) {
- for (int columnNumber = 0; columnNumber < tableWidth; ++columnNumber) {
- if (table[rowNumber][columnNumber] == '*')
- continue;
- int cellCode = getCellCode(tableWidth, rowNumber, columnNumber);
- for (int adjacentCellColumn = columnNumber - 1; adjacentCellColumn >= 0; --adjacentCellColumn) {
- if (table[rowNumber][adjacentCellColumn] == '*')
- break;
- else {
- graph[cellCode].push_back(getCellCode(tableWidth, rowNumber, adjacentCellColumn));
- }
- }
- for (int adjacentCellColumn = columnNumber + 1; adjacentCellColumn < tableWidth; ++adjacentCellColumn) {
- if (table[rowNumber][adjacentCellColumn] == '*')
- break;
- else {
- graph[cellCode].push_back(getCellCode(tableWidth, rowNumber, adjacentCellColumn));
- }
- }
- for (int adjacentCellRow = rowNumber - 1; adjacentCellRow >= 0; --adjacentCellRow) {
- if (table[adjacentCellRow][columnNumber] == '*')
- break;
- else {
- graph[cellCode].push_back(getCellCode(tableWidth, adjacentCellRow, columnNumber));
- }
- }
- for (int adjacentCellRow = rowNumber + 1; adjacentCellRow < tableHeight; ++adjacentCellRow) {
- if (table[adjacentCellRow][columnNumber] == '*')
- break;
- else {
- graph[cellCode].push_back(getCellCode(tableWidth, adjacentCellRow, columnNumber));
- }
- }
- }
- }
- return graph;
- }
- int main()
- {
- int width, height;
- cin >> width >> height;
- vector<string> table(height);
- for (int rowNumber = 0; rowNumber < height; ++rowNumber) {
- cin >> table[rowNumber];
- }
- int firstCowRow = -1, firstCowColumn = -1;
- int secondCowRow = -1, secondCowColumn = -1;
- for (int rowNumber = 0; rowNumber < height; ++rowNumber) {
- for (int columnNumber = 0; columnNumber < width; ++columnNumber) {
- if (table[rowNumber][columnNumber] == 'C') {
- if (firstCowRow == -1 && firstCowColumn == -1) {
- firstCowRow = rowNumber;
- firstCowColumn = columnNumber;
- }
- else {
- secondCowRow = rowNumber;
- secondCowColumn = columnNumber;
- }
- }
- }
- }
- vector<vector<int> > graph = buildConnectivityGraph(table);
- vector<int> distances(graph.size());
- int startVertex = getCellCode(width, firstCowRow, firstCowColumn);
- int endVertex = getCellCode(width, secondCowRow, secondCowColumn);
- for (int vertexIterator = 0; vertexIterator < distances.size(); ++vertexIterator) {
- distances[vertexIterator] = INF;
- }
- distances[startVertex] = -1;
- queue<int> bfsQueue;
- bfsQueue.push(startVertex);
- while (!bfsQueue.empty()) {
- int currentVertex = bfsQueue.front();
- if (currentVertex == endVertex) {
- cout << distances[endVertex] << endl;
- return 0;
- }
- bfsQueue.pop();
- for (int adjacentVerticesIterator = 0; adjacentVerticesIterator < graph[currentVertex].size(); ++adjacentVerticesIterator) {
- if (distances[graph[currentVertex][adjacentVerticesIterator]] != INF)
- continue;
- distances[graph[currentVertex][adjacentVerticesIterator]] = distances[currentVertex] + 1;
- bfsQueue.push(graph[currentVertex][adjacentVerticesIterator]);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement