782 - Contour Painting

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mice123456789
New poster
Posts: 12
Joined: Tue Aug 27, 2002 6:09 pm

Re: 782 - Countour Painting

Post by mice123456789 » Wed Mar 03, 2010 4:43 am

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

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

Re: 782 - Countour Painting

Post by qwerty » Wed Mar 03, 2010 8:45 am

thanks mice for ur help.Accepted at last.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 782 - Countour Painting

Post by zobayer » Wed Feb 02, 2011 10:40 am

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 :oops:
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.
You should not always say what you know, but you should always know what you say.

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re:

Post by mostafiz93 » Sun Apr 29, 2012 3:04 am

angga888 wrote: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 ! :D

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 782 - Countour Painting

Post by brianfry713 » Thu Jul 10, 2014 8:00 pm

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.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 782 - Countour Painting

Post by jddantes » Wed Aug 20, 2014 1:12 pm

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
Last edited by jddantes on Thu Aug 21, 2014 2:51 am, edited 2 times in total.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 782 - Countour Painting

Post by jddantes » Wed Aug 20, 2014 1:56 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 782 - Countour Painting

Post by brianfry713 » Wed Aug 20, 2014 9:19 pm

In the second version of your code you are printing a space on the blank lines.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 782 - Countour Painting

Post by jddantes » Thu Aug 21, 2014 2:50 am

Thanks!

Post Reply

Return to “Volume 7 (700-799)”