785 - Grid Colouring

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

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

785

Post by QulinXao » Tue Feb 21, 2006 1:41 am

I think in some test was error.
in string where must only 1 or more '_'
as state in problem: each grid is terminated by a separation line full of underscores `_'.
judge (if see carefull test file for 785 ) may wotch
that situeted ' '(I think on end of string full of underscores `_' )

base on that some good sol get wa
then piple chit and think that '_' can't be the marking characters
and 'X' to can't be the marking characters
pls add test where contours is other than 'X'
and '_' and 'X' is marking characters
and DELETE all but '_' chars from string witch end evry grid

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Apr 27, 2006 8:29 am

My problem was that I assumed that there were at most 30 lines in a grid. 35 worked.

I don't know, maybe I made some stupid mistake, but otherwise that problem description should be changed.

Darko

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Mon Apr 16, 2007 7:28 am

My problem was that I assumed that there were at most 80 characters per line.

When I changed to 81, like cin.getline(input, 81) or just gets(input), it passed.

/sjn

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Apr 16, 2007 7:56 am

sjn wrote:My problem was that I assumed that there were at most 80 characters per line.

When I changed to 81, like cin.getline(input, 81) or just gets(input), it passed.

/sjn
Actually, your assumption was right.
cin.getline(input, 80) means inputs 80 character including \0, so it actually reads 79 character.

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Mon Apr 16, 2007 8:43 am

rio wrote: Actually, your assumption was right.
cin.getline(input, 80) means inputs 80 character including \0, so it actually reads 79 character.
many thx for your explanation! it seems trivial, but great to me!

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Mon May 07, 2007 8:33 am

why m is 30.
m most be 80

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 785 - Grid Colouring

Post by x140l31 » Fri Oct 24, 2008 10:43 pm

can anyone help me?

I get RE! why?

Code: Select all

#include <iostream>
using namespace std;

void floodFill(char map[31][81], int i, int j, char fill)
{
    map[i][j] = fill;
    if (map[i - 1][j] == ' ') floodFill(map, i - 1, j, fill);
    if (map[i + 1][j] == ' ') floodFill(map, i + 1, j, fill);
    if (map[i][j - 1] == ' ') floodFill(map, i, j - 1, fill);
    if (map[i][j + 1] == ' ') floodFill(map, i, j + 1, fill);
}

int main()
{
    int c;
    char map[31][81];
    while (scanf("%[^\n]", map[0]) != EOF)
    {
        int ii = 0;
        while (map[ii][0] != '_')
        {
            cin.ignore();
            scanf("%[^\n]", map[++ii]);
        }

        char wall = '\0';
        for (int i = 0; i < ii; ++i)
        {
            for (int j = 0; map[i][j] != '\0'; ++j)
            {
                if (wall == '\0' and map[i][j] != ' ') wall = map[i][j];
                else if (map[i][j] != ' ' and map[i][j] != wall) floodFill(map, i, j, map[i][j]);
            }
        }

        for (int i = 0; i <= ii; ++i) printf("%s\n", map[i]);
        for (int i = 0; i < 31; ++i)
            for (int j = 0; j < 81; ++j) map[i][j] = '\0';
    }
}

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 785 - Grid Colouring

Post by Obaida » Wed Mar 10, 2010 8:59 am

Every one getting WA please take a look at this line:-

Code: Select all

A zone is marked if it contains identical characters, called marking characters, different than space and the character used to draw the grid contours.
I got wA for this. :wink:
try_try_try_try_&&&_try@try.com
This may be the address of success.

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

Re: 785 - Grid Colouring

Post by Eather » Mon Apr 18, 2011 12:43 am

Where's to end of the output. I am getting TLE. please help me someone.

Code: Select all

                           /*in the name of Allah */
# include <list>
# include <deque>
# include <bitset>
# include <algorithm>
# include <functional>
# include <numeric>
# include <utility>
# include <sstream>
# include <iostream>
# include <iomanip>
# include <cstdio>
# include <cmath>
# include <cstdlib>
# include <ctime>
# include <set>
# include <map>
# include <cmath>
# include <queue>
# include <limits>
# include <stack>
# include <vector>
# include <cstring>
# include <cstdio>
using namespace std;

# define MEM(array,w)   memset(array,w,sizeof array)
# define ULL unsigned long long
# define eps 1e-9
# define SS stringstream
# define PR pair<int , int>
# define all(c) (c).begin(), (c).end()
# define FOR(i, a, b) for (int i=a; i<b; i++)
# define REP(i, a) FOR(i, 0, a)
# define rive(s) reverse(s.begin(),s.end())
# define OK(R,C) if(i>=0 && j>=0 && j<=C && i<=R)

# define MPSS map<string, string>
# define MPIS map<int, string>
# define MPSI map<string, int>
# define MPII map<int, int>
# define MPIC map<int,char>
# define MPCI map<char, int>

# define VS vector<string>
# define VI vector<int>
# define VC vector<char>
# define VB vector<bool>
# define pb push_back
# define mp make_pair


template<class T> string toString(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}

int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}

bool isprime(int n){if( n<2) return 0;for( int i=2; i*i<=n ; i++)if(n%i==0)return 0; return 1;return 0;}

int pel(string s){string t;t=s;reverse(t.begin(),t.end());if(s==t)return 1;return 0;}

int row,col;
char maze[40][90];
vector< pair<int, int> >vp;
bool visited[40][90];

int dr [] = {1,-1,0,0};


int dc [] = {0,0,1,-1};

void dfs(int i, int j, char ch)
{

  if(i<0||j<0||i>vp[i].first|| j>vp[i].second||maze[i][j]=='X'||visited[i][j]==1)return;

  if(maze[i][j]==' ' || maze[i][j]==ch)
    maze[i][j]=ch;
  visited[i][j]=1;

  for ( int k = 0; k < 4; k++ )
        dfs (i + dr [k], j + dc [k],ch);
}
int main()
{

int test,Ctest=0;

while(1)
{
  char s[90];

  vp.clear();
  row=col=0;
  MEM(visited,0);
  char fin[81];
  while(gets(s))
  {
    if(s[0]!='_'){
    strcpy(maze[row],s);
    col=strlen(s);
    row++;
    vp.push_back(mp(row,col));
    }else
    {
      strcpy(fin,s);
      break;
    }
  }

  for(int i=0;i<vp.size();i++)
  {
   for(int j=0;j<vp[i].second;j++){
   while(maze[i][j]==' ')j++;
    if(maze[i][j]!=' '&&maze[i][j]!='X')
    {

      char ch;ch=maze[i][j];
      dfs(i,j,ch);
    }}
  }
  for(int i=0;i<vp.size();i++){
  for(int j=0;j<vp[i].second;j++)
  cout<<maze[i][j];
  cout<<endl;}cout<<fin<<endl;
}

return 0;
}

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 785 - Grid Colouring

Post by Scarecrow » Fri Jul 13, 2012 3:35 pm

Some are saying that the maximum row and column number is wrong stated in the problem. Actually the problem statement is OK and the maximum row and column numbers are 30 and 80 respectively. But a char array of size [31][81] should be taken for the accommodation of the underscore line after the last row and '\0' s in each column.
Do or do not. There is no try.

rosynirvana
New poster
Posts: 4
Joined: Thu Oct 03, 2013 10:16 pm

Re: 785 - Grid Colouring

Post by rosynirvana » Thu Oct 03, 2013 10:29 pm

Hello everyone:
I got RE with this problem the first time and then I enlarge the array of std::string and got AC.
So I think the really tricky part of this problem is that the blank line above and under the grid. They are not counted within the 30 lines. So an array of 30 rows could result in RE.
By the way, the description of the problem is somewhat misleading.
The contours are made of any printable character different than space and `_' (underscore). In the sample this character is `X'.
In fact the contours character can only be `X' or the problem cannot be solved. For example

Code: Select all

XXX
XAX
XXX

AAA
AAA
AAA
Now you cannot tell what is the contours and what is the marking.

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

Re: 785 - Grid Colouring

Post by ehsanulbigboss » Mon Mar 09, 2015 10:06 pm

Got some hints :)
Last edited by ehsanulbigboss on Thu Jul 09, 2015 10:13 pm, edited 1 time in total.

ocin_lr
New poster
Posts: 3
Joined: Sat Jun 27, 2015 7:52 pm

Re: 785 - Grid Colouring

Post by ocin_lr » Mon Jul 06, 2015 7:55 pm

Hi, Everyone,

I don't know for you, but for me this problem was a little bit tricky and the previous forum replies were not helpful enough. Here some Tips:

1- As suggested for this problem (and I recommend it also for all problems), you should use static arrays a little bit larger than the limits of the problem to avoid off-by-one Runtime Error.
2- The contours are not necessarily 'X' and the marking characters are not necessarily '/' and '#':

Code: Select all

  XXXXXXXXXXXXXXXXXXXX
  X      X           X
  X * *  XXXXXXXX .  X
  X             X    X
  XXXXXXXXXXXXXXXXXXXX
_____________________________

   XXXXXXXXXXXX       XXXXXX
  X       #   XXX  XXX   X X
  X  XX         X  X     X X
 X  X  X  XXXXXXX  XXXXXXX
 X   XX   X
  X       X  XXXX  XXXXXXXX
   XX     XXXX  X  X  /   X
    X           X  X    / X
    XXXXXXXXXXXXX  XXXXXXXX
_____________________________
  AAAAAAAAAAAAAAAAAAAA
  A      A           A
  A # #  AAAAAAAA /  A
  A             A    A
  AAAAAAAAAAAAAAAAAAAA
_____________________________

   AAAAAAAAAAAA       AAAAAA
  A       :   AAA  AAA   A A
  A  AA         A  A     A A
 A  A  A  AAAAAAA  AAAAAAA
 A   AA   A
  A       A  AAAA  AAAAAAAA
   AA     AAAA  A  A  /   A
    A           A  A    / A
    AAAAAAAAAAAAA  AAAAAAAA
_____________________________
Check the output at http://www.udebug.com/UVa/785

Post Reply

Return to “Volume 7 (700-799)”