Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- std::vector<std::vector<int>> parking;
- std::vector<std::vector<int>> graph;
- std::vector<std::vector<int>> tparking;
- std::vector<int> used;
- int n = 0, m = 0, numOfZeros = 0;
- int ent, ex;
- bool isThereTheWayVariable;
- void dfs (int v, int to){
- if(v == to)
- isThereTheWayVariable = true;
- used[v] = true;
- for(int i = 0; i < n * m; ++i) {
- if (graph[v][i] && !used[i]) {
- dfs(i, to);
- }
- }
- }
- bool isThereTheWay(int from, int to){
- if(from == to)
- return true;
- isThereTheWayVariable = false;
- used.assign(n * m, 0);
- dfs(from, to);
- return isThereTheWayVariable;
- }
- void buildGraphFromMap(){
- for(int i = 0; i < n; ++i){
- for(int j = 0; j < m; ++j){
- if(tparking[i][j] != 1 && i > 0 && tparking[i - 1][j] != 1){
- graph[i * m + j][i * m + j - m] = 1;
- graph[i * m + j - m][i * m + j] = 1;
- } if(tparking[i][j] != 1 && i < n - 1 && tparking[i + 1][j] != 1){
- graph[i * m + j][i * m + j + m] = 1;
- graph[i * m + j + m][i * m + j] = 1;
- } if(tparking[i][j] != 1 && j > 0 && tparking[i][j - 1] != 1){
- graph[i * m + j][i * m + j - 1] = 1;
- graph[i * m + j - 1][i * m + j] = 1;
- } if(tparking[i][j] != 1 && j < m - 1 && tparking[i][j + 1] != 1){
- graph[i * m + j][i * m + j + 1] = 1;
- graph[i * m + j + 1][i * m + j] = 1;
- }
- }
- }
- }
- void print2DVector(std::vector<std::vector<int>> toPrint){
- for(int i = 0; i < toPrint.size(); ++i)
- for(int j = 0; j < toPrint[i].size(); ++j)
- std::cout << toPrint[i][j] << (j == toPrint[i].size() - 1 ? "\n" : " ");
- }
- struct Mask{
- int size;
- std::vector<int> *vmask;
- Mask(int size){
- this->size = size;
- vmask = new std::vector<int> (size, 0);
- };
- bool addOne (){
- bool add = true;
- for(int i = size - 1; i >= 0; --i){
- if(!add)
- break;
- if((*vmask)[i] == 0)
- (*vmask)[i] = 5, add = false;
- else
- (*vmask)[i] = 0, add = true;
- }
- if(add)
- return false;
- else
- return true;
- }
- int sum(){
- int ans = 0;
- for(int i = 0; i < size; ++i)
- ans += (*vmask)[i];
- return ans;
- }
- void show(){
- std::cout << "showing\n";
- for(int i = 0; i < (*vmask).size(); ++i)
- std::cout << (*vmask)[i];
- std::cout << '\n';
- }
- };
- int main() {
- std::ifstream input("input.txt");
- input >> n >> m;
- std::cout << n << ' ' << m << '\n';
- // 0 is for space 1 is for obstacle
- parking.resize(n, std::vector<int> (m, 0));
- graph.resize(n * m, std::vector<int> (n * m, 0));
- for(int i = 0; i < parking.size(); ++i) {
- for (int j = 0; j < parking[i].size(); ++j) {
- input >> parking[i][j];
- if(!parking[i][j])
- numOfZeros++;
- if(parking[i][j] == 2)
- ent = i * m + j;
- if(parking[i][j] == 3)
- ex = i * m + j;
- }
- }
- Mask mask(numOfZeros);
- mask.addOne();
- auto bestParking = parking;
- int bestResult = 0;
- do{
- tparking = parking;
- int maskIndex = 0;
- for(int i = 0; i < n; ++i) { // расставляем парковки = 5
- for(int j = 0; j < m; ++j){
- if(tparking[i][j] == 0)
- tparking[i][j] = (*mask.vmask)[maskIndex], maskIndex++;
- }
- }
- buildGraphFromMap();
- bool isEnt, isEx, isNice = true;
- for(int i = 0; i < n; ++i) { // проверям что отовсюду можно выехать и везде заехать по свободным дорогам
- for(int j = 0; j < m; ++j){
- if(tparking[i][j] == 5){
- isEnt = false, isEx = false;
- isNice = true;
- if(i * m + j == ent)
- isEnt = true;
- if(i * m + j == ex)
- isEx = true;
- if (i > 0 && tparking[i - 1][j] != 1 && tparking[i - 1][j] != 5) {
- if (isThereTheWay(i * m + j - m, ex))
- isEx = true;
- if (isThereTheWay(i * m + j - m, ent))
- isEnt = true;
- }
- if (i < n - 1 && tparking[i + 1][j] != 1 && tparking[i + 1][j] != 5) {
- if (isThereTheWay(i * m + j + m, ex))
- isEx = true;
- if (isThereTheWay(i * m + j + m, ent))
- isEnt = true;
- }
- if (j > 0 && tparking[i][j - 1] != 1 && tparking[i][j - 1] != 5) {
- if (isThereTheWay(i * m + j - 1, ex))
- isEx = true;
- if (isThereTheWay(i * m + j - 1, ent))
- isEnt = true;
- }
- if (j < m - 1 && tparking[i][j + 1] != 1 && tparking[i][j + 1] != 5) {
- if (isThereTheWay(i * m + j + 1, ex))
- isEx = true;
- if (isThereTheWay(i * m + j + 1, ent))
- isEnt = true;
- }
- if (!isEnt || !isEx) {
- isNice = false;
- break;
- }
- }
- }
- if(!isNice)
- break;
- }
- if(isNice && mask.sum() > bestResult)
- bestResult = mask.sum(), bestParking = tparking;
- } while(mask.addOne());
- std::cout << "max parking places - " << bestResult << '\n';
- print2DVector(bestParking);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement