Messages posted by: mitkonikov

MOI wrote:

mitkonikov wrote:Ja resavam zadachata so BFS od sekoe cveke.... 100 BFS najlos sluchaj ke bide CxNxM 100x(1000x1000) t.e. na cela zadaca => 100 000 000
Za site primeri raboti, samo na cetvrtiot ne.....

Во текстот на задачата пишува:
"Цревата на системот не може да поминат преку полињата со бетонски плочи, но слободно може да поминуваат преку сите други полиња."

Во твојата функција valid(), проверуваш дали (c[a][b] == '.'), а мислам дека треба да биде (c[a][b] == '.' || c[a][b] == 'C').
Го пратив тоа решение, и поминува на сите примери.

Taka e.... Pretpostaviv deka crevoto ne moze da pomine niz cveketo.... Ne se fokusirav na tekstot, bidejki raboteshe na mnogu primeri. Blagodaram!

Ja resavam zadachata so BFS od sekoe cveke.... 100 BFS najlos sluchaj ke bide CxNxM 100x(1000x1000) t.e. na cela zadaca => 100 000 000
Za site primeri raboti, samo na cetvrtiot ne.....

Kako ja resavam :
BFS od sekoe cveke do moknosta, i na glavna matrica (matrix[1000][1000]) na polinata na koi mine BFS-to inkrementiram
i potoa na krajot, samo ja gledam najgolemata brojka so prioritet na onie sto se levo gore...

Blagodaram odnapred....

///
/// FAILS JUST AT THE FOURTH TEST CASE
/// LINK TO THE TEST CASE DOWNLOADED :
/// https://www.dropbox.com/s/21e7x5v2259rtuo/TEST_704_4.zip?dl=0
///
/// LINK TO THE PROBLEM : http://mendo.mk/Task.do?id=704
///
 
#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
 
int matrix[1000][1000]; // MAIN MATRIX
int c[1000][1000];      // BFS CHAR MATRIX
int a[1000][1000];      // BFS SEARCH MATRIX
queue<  pair<int, int>  > flowers;
int width, height;
 
bool valid(int a, int b) {
    if (a >= 0 && b >= 0 && a < height && b < width && c[a][b] == '.')
        return true;
    return false;
}
 
void printArray(int b[1000][1000]) { // TEMP FUNC FOR DEBUGGING
    cout << endl;
    for (int i = 0; i < height; ++i) {
        for (int j = 0; j < width; ++j) {
            cout << setw(8) << b[i][j];
        }
        cout << endl;
    }
    cout << endl;
}
 
int main()
{
    ios::sync_with_stdio(0);
 
    cin >> height >> width;
 
    int Power;
    cin >> Power;
 
    for (int i = 0; i < height; ++i) {
        for (int j = 0; j < width; ++j) {
            char current;
            cin >> current;
            c[i][j] = current;
            matrix[i][j] = 0;
            a[i][j] = 101000;
 
            if (current == 'C') {
                flowers.push(make_pair(i, j));
            }
        }
    }
 
    int counter = 1;
    while (!flowers.empty()) {
        queue<  pair<int, int>  > q;
        pair<int, int> cur = flowers.front();
        q.push(cur);
        flowers.pop();
        a[cur.f][cur.s] = 101000 - counter * 1000;
 
        // BFS
        while (!q.empty()) {
            pair<int, int> current = q.front();
            q.pop();
            if (a[current.f][current.s] + 1 - (101000 - counter * 1000) <= Power) {
                if (valid(current.f + 1, current.s) && a[current.f + 1][current.s] > a[current.f][current.s] && a[current.f + 1][current.s] > 101000 - (counter + 1) * 1000 && a[current.f + 1][current.s] != a[current.f][current.s] + 1) {
                    a[current.f + 1][current.s] = a[current.f][current.s] + 1;
                    matrix[current.f + 1][current.s]++;
                    q.push(make_pair(current.f + 1, current.s));
                }
                if (valid(current.f, current.s + 1) && a[current.f][current.s + 1] > a[current.f][current.s] && a[current.f][current.s + 1] > 101000 - (counter + 1) * 1000 && a[current.f][current.s + 1] != a[current.f][current.s] + 1) {
                    a[current.f][current.s + 1] = a[current.f][current.s] + 1;
                    matrix[current.f][current.s + 1]++;
                    q.push(make_pair(current.f, current.s + 1));
                }
                if (valid(current.f - 1, current.s) && a[current.f - 1][current.s] > a[current.f][current.s] && a[current.f - 1][current.s] > 101000 - (counter + 1) * 1000 && a[current.f - 1][current.s] != a[current.f][current.s] + 1) {
                    a[current.f - 1][current.s] = a[current.f][current.s] + 1;
                    matrix[current.f - 1][current.s]++;
                    q.push(make_pair(current.f - 1, current.s));
                }
                if (valid(current.f, current.s - 1) && a[current.f][current.s - 1] > a[current.f][current.s] && a[current.f][current.s - 1] > 101000 - (counter + 1) * 1000 && a[current.f][current.s - 1] != a[current.f][current.s] + 1) {
                    a[current.f][current.s - 1] = a[current.f][current.s] + 1;
                    matrix[current.f][current.s - 1]++;
                    q.push(make_pair(current.f, current.s - 1));
                }
            }
 
 
            // printArray(a);
        }
 
        counter++;
 
        // printArray(a);
        // printArray(matrix);
    }
 
    int bx, by, best = 0;
    for (int k = 0; k < height; ++k) {
        for (int p = 0; p < width; ++p) {
            if (matrix[k][p] > best) {
                best = matrix[k][p];
                by = k + 1;
                bx = p + 1;
            }
        }
    }
 
    cout << by << " " << bx << endl;
 
    return 0;
}

Eve video koe go napraviv za ovaa zadaca!
https://www.youtube.com/watch?v=6zcFB1nIoq8