/** ************************************************************************* --- Honey Heist --- Graph based solution for MCPC 2017 R. Marshall Input The first 5 lines of input contain a single integer each, as follows: R: the length (number of cells) of each edge of the grid, where 2 <= R <= 20. The total number of cells in the grid can be determined by taking a difference of cubes, $R^3 - (R-1)^3$. N: the maximum number of cells 0x67 can chew through, where 1 <= N < R^3 - (R-1)^3. A: the starting cell ID, assume this cell is located on one of the grid edges. B: the ID of the cell containing the honey, where B <> A. X: the number of wax-hardened cells, where 0 <= X < ( R^3 - (R-1)^3 ) - 1, followed by $X$ integers on a single line separated by spaces, where each integer is the ID of the cell. Output A single integer K if the path from A to B (where B is the Kth cell) is no more than N, otherwise the string "No". compile: g++ -std=c++11 -o hh honeyheist.cpp run: ./hh ************************************************************************* */ #include #include #include #include #include #include #include #include using namespace std; multimap g_hcomb; // main honeycomb vector g_walls; // list of wall cells typedef std::multimap::iterator found_itr; void add_edge(int from, int to) { if (std::find(g_walls.begin(), g_walls.end(), to) == g_walls.end() && std::find(g_walls.begin(), g_walls.end(), from) == g_walls.end() ) { g_hcomb.insert(std::pair(from, to) ); } } int BFS(int A, int B, int ncells) { int start = A; bool *visited = new bool[ncells+1]; for (int i = 0; i <= ncells; i++) visited[i] = false; visited[A] = true; list queue; list::iterator it; vector pre; queue.push_back(A); pre.resize(ncells+1); pre.at(A) = -1; bool found = false; while ( !queue.empty() && !found) { A = queue.front(); queue.pop_front(); if (A == B) { found = true; } else { list adj; std::pair ret = g_hcomb.equal_range(A); for (found_itr it = ret.first; it != ret.second; ++it) adj.push_back(it->second); for (it = adj.begin(); it != adj.end(); it++) { if ( ! visited[*it]) { visited[*it] = true; pre.at(*it) = A; queue.push_back(*it); } } } } int current = B, pathsz = 1; list path; path.push_back(current); while (current != start && pathsz <= ncells) { // backtrace the path current = pre.at(current); path.push_back(current); pathsz++; } return (path.size() - 1); // final answer } int main(int argc, char* argv[]) { int R, N, A, B, X, x ; cin >> R >> N >> A >> B >> X; for (int i = 0; i < X; i++) { cin >> x; g_walls.push_back(x); } // ------------------------------------------------------- // int numcells = (pow(R,3.0) - pow(R-1,3.0)); // total num cells int zrowsz = ((R * 2) - 1); // size of largest row int rsz = R; // adjustable row size int cell = 1; // cell ID for (int i = 1; i <= zrowsz; i++) { for (int j = 1; j <= rsz; j++) { if (j > 1) add_edge(cell, cell-1); // ww if (j < rsz) add_edge(cell, cell+1); // ee if (i == 1) { // top edge cells add_edge(cell, cell+rsz); // sw uh add_edge(cell, cell+rsz+1); // se uh } else if (i == zrowsz) { //bottom edge cells add_edge(cell, cell-(rsz+1)); // ne lh add_edge(cell, cell-rsz); // nw lh } else { // rows not top or bottom if (i > R) { add_edge(cell, cell-rsz); // ne lh* add_edge(cell, cell-(rsz+1)); // nw lh* if (j > 1) add_edge(cell, cell+(rsz-1)); // sw lh if (j < rsz) add_edge(cell, cell+rsz); // se lh* } else if (i < R) { add_edge(cell, cell+rsz+1); // se uh add_edge(cell, cell+rsz); // sw uh if (j > 1) add_edge(cell, cell-rsz); // nw uh if (j < rsz) add_edge(cell, cell-(rsz-1)); // ne uh } else { // R if (j < rsz) { add_edge(cell, cell-(rsz-1)); // ne add_edge(cell, cell+rsz); // se } if (j > 1) { add_edge(cell, cell-rsz); // nw add_edge(cell, cell+(rsz-1)); // sw } } } cell++; } rsz = (i < R) ? rsz +1 : rsz -1; } int answer = BFS(A,B,numcells); if (answer <= N) cout << answer; else cout << "No"; cout << endl; return 0; }