## 782 - Contour Painting

Moderator: Board moderators

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

### Re: 782 - Countour Painting

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

### Re: 782 - Countour Painting

thanks mice for ur help.Accepted at last.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 782 - Countour Painting

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?

Code: Select all

``````AC
``````

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:

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

### Re: 782 - Countour Painting

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

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;

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

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;

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

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

Thanks!