Градинар

This message was edited 1 time. Last update was at 09/03/2019 17:29:03

http://mendo.mk/Task.do?id=704

Знае ли некој зошто не ми поминува на 1/10 тест случаи (на 4тиот мојот код дава резултат 1 23, а треба 1 21)?

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <climits>
#include <cfloat>
#include <cstdlib>

#define pb push_back

using namespace std;

const int MAXN = 101;
const int MAXV = 1000000000;

int rows, cols, power, M = 0;
vector <vector <int> > graph(MAXN*10, vector <int> (MAXN*10));

struct state {
    int x, y;
};

bool validMove(state next) {
    return (next.x >= 0 && next.x < rows && next.y >= 0 && next.y < cols &&
            graph[next.x][next.y] != -1);
}

vector <state> possibleMoves(state node) {
    vector <state> moves;
    moves.pb({node.x, node.y-1});
    moves.pb({node.x, node.y+1});
    moves.pb({node.x-1, node.y});
    moves.pb({node.x+1, node.y});
    return moves;
}

bool bfs(state s, vector <vector <bool> > visited, vector <vector <int> > nGraph) {
    queue <state> q;
    q.push(s);

while (!q.empty()) {
        auto node = q.front();
        q.pop();
        vector <state> moves = possibleMoves(node);

for (auto next : moves) {
            if (validMove(next)) {
                if (!visited[next.x][next.y]) {
                    visited[next.x][next.y] = true;
                    if (nGraph[next.x][next.y] > nGraph[node.x][node.y] + 1) {
                        nGraph[next.x][next.y] = nGraph[node.x][node.y] + 1;
                        if (nGraph[next.x][next.y] <= power) {
                            q.push(next);
                            graph[next.x][next.y]++;
                            M = max(M, graph[next.x][next.y]);
                        }
                    }
                }
            }
        }
    }
}

int main() {
    cin >> rows >> cols >> power;

queue <state> q;
    vector <vector <bool> > visited(MAXN*10, vector <bool> (MAXN*10, false));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            char c;
            cin >> c;
            if (c == '#') graph[i][j] = -1;
            else if (c == 'C') {
                graph[i][j] = 0;
                q.push({i, j});
                visited[i][j] = true;
            }
            else graph[i][j] = MAXV;
        }
    }

vector <vector <int> > nGraph = graph;
    graph = vector <vector <int> > (MAXN*10, vector <int> (MAXN*10, 0));

while (!q.empty()) {
        state s = q.front();
        q.pop();
        bfs(s, visited, nGraph);
    }

for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
//            cout << graph[i][j] << " ";
            if (graph[i][j] == M) {
                cout << i+1 << " " << j+1;
                return 0;
            }
        }
//        cout << endl;
    }

return 0;
}

floreloriz123 wrote:http://mendo.mk/Task.do?id=704

Знае ли некој зошто не ми поминува на 1/10 тест случаи (на 4тиот мојот код дава резултат 1 23, а треба 1 21)?

Ај види го следниот код (таму каде што е поправено) и размисли зошто овој работи на сите примери.
Хинт: И зошто тоа има врска со ова "Цревата на системот не може да поминат преку полињата со бетонски плочи, но слободно може да поминуваат преку сите други полиња.", и фактот што долу за секое 'C' викаш graph[i][j] = 0; visited[i][j] = true;

P.S. Пробав да променам најмалку работи во кодот, па затоа само сменив во функцијата bfs(), инаку ова може да се поедностави.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <climits>
#include <cfloat>
#include <cstdlib>

#define pb push_back

using namespace std;

const int MAXN = 101;
const int MAXV = 1000000000;

int rows, cols, power, M = 0;
vector <vector <int> > graph(MAXN*10, vector <int> (MAXN*10));

struct state {
    int x, y;
};

bool validMove(state next) {
    return (next.x >= 0 && next.x < rows && next.y >= 0 && next.y < cols &&
            graph[next.x][next.y] != -1);
}

vector <state> possibleMoves(state node) {
    vector <state> moves;
    moves.pb({node.x, node.y-1});
    moves.pb({node.x, node.y+1});
    moves.pb({node.x-1, node.y});
    moves.pb({node.x+1, node.y});
    return moves;
}

bool bfs(state s, vector <vector <bool> > &visited, vector <vector <int> > &nGraph) {
    queue <state> q;
    q.push(s);
    
    //dodadeno
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            visited[i][j] = false;
            
            if (nGraph[i][j] != -1) {
                nGraph[i][j] = MAXV;
            }
        }
    }

nGraph[s.x][s.y] = 0;
    visited[s.x][s.y] = true;

while (!q.empty()) {
        auto node = q.front();
        q.pop();
        vector <state> moves = possibleMoves(node);

for (auto next : moves) {
            if (validMove(next)) {
                if (!visited[next.x][next.y]) {
                    visited[next.x][next.y] = true;
                    if (nGraph[next.x][next.y] > nGraph[node.x][node.y] + 1) {
                        nGraph[next.x][next.y] = nGraph[node.x][node.y] + 1;
                        if (nGraph[next.x][next.y] <= power) {
                            q.push(next);
                            graph[next.x][next.y]++;
                            M = max(M, graph[next.x][next.y]);
                        }
                    }
                }
            }
        }
    }
}

int main() {
    cin >> rows >> cols >> power;

queue <state> q;
    vector <vector <bool> > visited(MAXN*10, vector <bool> (MAXN*10, false));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            char c;
            cin >> c;
            if (c == '#') graph[i][j] = -1;
            else if (c == 'C') {
                graph[i][j] = 0;
                q.push({i, j});
                visited[i][j] = true;
            }
            else graph[i][j] = MAXV;
        }
    }

vector <vector <int> > nGraph = graph;
    graph = vector <vector <int> > (MAXN*10, vector <int> (MAXN*10, 0));

while (!q.empty()) {
        state s = q.front();
        q.pop();
        bfs(s, visited, nGraph);
    }

for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
//            cout << graph[i][j] << " ";
            if (graph[i][j] == M) {
                cout << i+1 << " " << j+1;
                return 0;
            }
        }
//        cout << endl;
    }

return 0;
}

Аха. Фала