782 - Contour Painting

[mice123456789]

Careful with your input/output. Doesn't seem it read all inputs

[qwerty]

thanks mice for ur help.Accepted at last.

[zobayer]

http://uva.onlinejudge.org/external/7/782.html

Each contour is placed on its grid in such a way that it is fully surrounded by free grid points (spaces).

Then why the first test case have no spaces on the left side?
However, getting RTE... can't find the reason
Isn't grid[32][96] enough for this problem?

Here is my code, please help:

Code: Select all

AC

[Edit]
There are more than 30 rows, I used 32 and got RTE, setting it 40 passes.
I think, there are cases where there is no * at all.
Be careful to print the separator as provided in input.
No trailing space, or extra blank lines.

[mostafiz93]

At first, I also used algorithm just exactly like yours, but I got WA for several times. After I changed the algorithm, finally I got Accepted.
This is my algorithm :
1. Read grid until a line start with "_"
2. Find the position of asterisk.
3. I do not use one variable to store the border character. So any printable char except {*,space,_,#} can be border. My program can handle this input :

Code: Select all

XKHDKJS
J  *  D
JLNLKJN
__________

P.S: I don't know if that's a valid input or not, but it's better if you can handle it.
4. Use floodfill starting from position of asterisk. If row-1 or row+1 or col-1 or col+1 is a border, then change that position to "#".

That's all I did, hope you can get it Accepted soon.
Good Luck !

Best regards,
angga888

i got ac without checking multiple variable and i think judge data doesn't contain multiple variable.
representing the output in given form is a challenge in this problem!

[brianfry713]

Here is how I got AC in this problem.

Read the grid until a line starts with _.
Fill the end of each line up to column 81 with spaces.

Starting with the * position, flood fill each space with a #.

For every # in the grid, change it to a space if there is not a X neighbor (I safely assumed the judge's input only uses the character X).
Remove all trailing spaces.
Print the grid.

[jddantes]

Why WA?

Code: Select all

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main(){
    char buff[2000];
    fgets(buff, 2000, stdin);
    int cases;
    sscanf(buff,"%d", &cases);

    for(int e = 0; e<cases; e++){
        vector< vector<char> > grid;
        vector< vector<int> > arr;
        vector<int> rowLen;
        vector<char> sep;

        char contourMarking;
        int maxlen = 0;
        while(fgets(buff, 2000, stdin)!=NULL){
            if(buff[0] == '_'){
                for(int x = 0; buff[x] != '\n' && buff[x]!='\r' && buff[x]; x++){
                    sep.push_back(buff[x]);
                }
                /*printf("%s", buff);
                printf("Got sep: %d\n", sep.size());
                for(int x = 0; x<sep.size(); x++){
                    printf("%c", sep[x]);
                }
                printf("\n");*/
                break;
            } else {
                vector<char> row;
                int len = 0;
                for(int x = 0; buff[x]!='\n'&& buff[x]!='\r'; x++){
                    if(buff[x] !=' ' && buff[x] !='*'){
                        contourMarking = buff[x];
                    }

                    row.push_back(buff[x]);
                    len++;
                }
                if(len>maxlen){
                    maxlen = len;
                }
                grid.push_back(row);
                rowLen.push_back(len);
                arr.push_back(vector<int>(len, 0));
                //printf("%s", buff);
            }
        }
        maxlen++;

        // Done with input



        int numRows = grid.size();

        // Check input
        for(int i = 0; i<numRows; i++){break;
            for(int j = 0; j<rowLen[i]; j++){
                printf("%c", grid[i][j]);
            }
            printf("\n");
        }

        /*for(int x = 0; x<numRows; x++){
            grid[x].resize(maxlen, ' ');
        }*/

        //int numCols = grid[0].size();
        //arr.assign(numRows, vector<int>(numCols, 0));


        int groupId = 0;
        for(int i = 0; i<numRows; i++){//break;
            for(int j = 0; j<rowLen[i]; j++){
                //printf("%c", grid[i][j]);
                if(grid[i][j]!='*'){
                    continue;
                }

                // Flood fill interior/exterior
                pair<int, int> src = make_pair(i,j);
                queue< pair<int, int> > que;
                que.push(src);

                groupId++;
                while(!que.empty()){
                    pair<int, int> currentNode = que.front();
                    que.pop();
                    if(arr[currentNode.first][currentNode.second]){
                        continue;
                    }
                    arr[currentNode.first][currentNode.second] = groupId;

                    // Push adj
                    for(int x = 0; x<4; x++){
                        int I = currentNode.first + dy[x];
                        int J = currentNode.second + dx[x];
                        if(I<0 || J<0 || I>=numRows){
                            continue;
                        }
                        if(J>=rowLen[I]){
                            continue;
                        }
                        if(arr[I][J]){
                            continue;
                        }
                        if(grid[I][J]!=' ' && grid[I][J]!='*'){
                            continue;
                        }
                        que.push(make_pair(I, J));
                    }
                } // End bfs loop
                //printf("Bfs ended\n");

            }
            //printf("\n");
        } // End flood fill loop
        //printf("Done flooding\n");
        // Paint
        for(int i = 0; i<numRows; i++){//break;
            for(int j = 0; j<rowLen[i]; j++){
                if(grid[i][j]!=contourMarking){
                    continue;
                }
                // Paint
                for(int x = 0; x<4; x++){
                    int I = i + dy[x];
                    int J = j + dx[x];
                    if(I<0 || J<0 || I>=numRows){
                        continue;
                    }
                    if(J>=rowLen[I]){
                        continue;
                    }
                    if(grid[I][J] == '#'){
                        continue;
                    }
                    if(arr[I][J]){
                        arr[I][J] = -1;
                    }
                }
            }
        }

        /*printf("@@@\n");
        for(int i = 0; i<numRows; i++){
            for(int j = 0; j<maxlen; j++){
                printf("%3d ", arr[i][j]);
            }
            printf("\n");
        }
        printf("@@@\n");
        */
        // Output
        for(int i = 0; i<numRows; i++){//break;
            for(int j = 0; j<rowLen[i]; j++){
                if(arr[i][j] == -1){
                    printf("#");
                } else {
                    if(grid[i][j] == '*'){
                        printf(" ");
                    } else {
                        printf("%c", grid[i][j]);
                    }
                }
            }
            printf("\n");
        }
        //printf("%d\n", sep.size());
        for(int x = 0; x<sep.size(); x++){
            printf("%c", sep[x]);
        }
        printf("\n");

    } // End cases loop

    return 0;
}

In a first version I tried to set the grid to a rectangular box (to pad the rightmost x's with spaces) but got PE:

Code: Select all

AC

edit: this second version was trimmed too

[jddantes]

I tried to trim spaces, but still got WA:

Code: Select all

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main(){
    char buff[2000];
    fgets(buff, 2000, stdin);
    int cases;
    sscanf(buff,"%d", &cases);

    for(int e = 0; e<cases; e++){
        vector< vector<char> > grid;
        vector< vector<int> > arr;
        vector<int> rowLen;
        vector<char> sep;

        char contourMarking;
        int maxlen = 0;
        while(fgets(buff, 2000, stdin)!=NULL){
            if(buff[0] == '_'){
                for(int x = 0; buff[x] != '\n' && buff[x]!='\r' && buff[x]; x++){
                    sep.push_back(buff[x]);
                }
                /*printf("%s", buff);
                printf("Got sep: %d\n", sep.size());
                for(int x = 0; x<sep.size(); x++){
                    printf("%c", sep[x]);
                }
                printf("\n");*/
                break;
            } else {
                vector<char> row;
                int len = 0;
                for(int x = 0; buff[x]!='\n'&& buff[x]!='\r'; x++){
                    if(buff[x] !=' ' && buff[x] !='*'){
                        contourMarking = buff[x];
                    }

                    row.push_back(buff[x]);
                    len++;
                }
                if(len>maxlen){
                    maxlen = len;
                }
                grid.push_back(row);
                rowLen.push_back(len);
                arr.push_back(vector<int>(len, 0));
                //printf("%s", buff);
            }
        }
        maxlen++;

        // Done with input



        int numRows = grid.size();

        // Check input
        for(int i = 0; i<numRows; i++){break;
            for(int j = 0; j<rowLen[i]; j++){
                printf("%c", grid[i][j]);
            }
            printf("\n");
        }

        /*for(int x = 0; x<numRows; x++){
            grid[x].resize(maxlen, ' ');
        }*/

        //int numCols = grid[0].size();
        //arr.assign(numRows, vector<int>(numCols, 0));


        int groupId = 0;
        for(int i = 0; i<numRows; i++){//break;
            for(int j = 0; j<rowLen[i]; j++){
                //printf("%c", grid[i][j]);
                if(grid[i][j]!='*'){
                    continue;
                }

                // Flood fill interior/exterior
                pair<int, int> src = make_pair(i,j);
                queue< pair<int, int> > que;
                que.push(src);

                groupId++;
                while(!que.empty()){
                    pair<int, int> currentNode = que.front();
                    que.pop();
                    if(arr[currentNode.first][currentNode.second]){
                        continue;
                    }
                    arr[currentNode.first][currentNode.second] = groupId;

                    // Push adj
                    for(int x = 0; x<4; x++){
                        int I = currentNode.first + dy[x];
                        int J = currentNode.second + dx[x];
                        if(I<0 || J<0 || I>=numRows){
                            continue;
                        }
                        if(J>=rowLen[I]){
                            continue;
                        }
                        if(arr[I][J]){
                            continue;
                        }
                        if(grid[I][J]!=' ' && grid[I][J]!='*'){
                            continue;
                        }
                        que.push(make_pair(I, J));
                    }
                } // End bfs loop
                //printf("Bfs ended\n");

            }
            //printf("\n");
        } // End flood fill loop
        //printf("Done flooding\n");
        // Paint
        for(int i = 0; i<numRows; i++){//break;
            for(int j = 0; j<rowLen[i]; j++){
                if(grid[i][j]!=contourMarking){
                    continue;
                }
                // Paint
                for(int x = 0; x<4; x++){
                    int I = i + dy[x];
                    int J = j + dx[x];
                    if(I<0 || J<0 || I>=numRows){
                        continue;
                    }
                    if(J>=rowLen[I]){
                        continue;
                    }
                    if(grid[I][J] == '#'){
                        continue;
                    }
                    if(arr[I][J]){
                        arr[I][J] = -1;
                    }
                }
            }
        }

        /*printf("@@@\n");
        for(int i = 0; i<numRows; i++){
            for(int j = 0; j<maxlen; j++){
                printf("%3d ", arr[i][j]);
            }
            printf("\n");
        }
        printf("@@@\n");
        */

        // Trailing spaces
        vector<int> ts(numRows, 0);
        for(int i = 0; i<numRows; i++){
            for(int j = 0; j<rowLen[i]; j++){
                if(arr[i][j] == -1 || grid[i][j] == contourMarking){
                   // printf("Marking j = %d\n", j);
                    ts[i] = j;
                }
            }
        }
        /*for(int x = 0; x<numRows; x++){
            printf("%d %d ", ts[x], rowLen[x]);
            if( ts[x] < rowLen[x]){
                printf("True\n");
            } else {
                printf("False\n");
            }
        }*/
        // Output
        /*printf("Waw\n");
        for(int i = 0; i<numRows; i++){
            printf("%d %d: ", ts[i], rowLen[i]);
            for(int j = 0; j<rowLen[i]; j++){
                printf("%c ", grid[i][j]);
            }
            printf("\n");
        }*/
        //printf("%d \n", arr[0][0]);
        //printf("%c\n", grid[0][0]);
        /*for(int x = 0; x<numRows; x++){
            printf("%d %d %d %d\n", ts[x], rowLen[x], grid[x].size(), arr[x].size());
        }*/
        for(int i = 0; i<numRows; i++){//break;
            //printf("Accessing row %d: ", i);

            if(arr[i].size() == 0){
                continue;
            }

            for(int j = 0; j<=ts[i]; j++){
                //printf("(%d %d) ",i, j);
                //printf("%d ", arr[i][j]);
                //printf("%c ", grid[i][j]);
                if(arr[i][j] == -1){
                    printf("#");

                } else {
                    if(grid[i][j] == '*'){
                        printf(" ");
                    } else {
                        printf("%c", grid[i][j]);
                    }
                }
            }
            printf("\n");
        }
        //printf("%d\n", sep.size());
        for(int x = 0; x<sep.size(); x++){
            printf("%c", sep[x]);
        }
        printf("\n");

    } // End cases loop

    return 0;
}

[brianfry713]

In the second version of your code you are printing a space on the blank lines.

[jddantes]

Thanks!