Page 2 of 2

785

Posted: Tue Feb 21, 2006 1:41 am
by QulinXao
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

Posted: Thu Apr 27, 2006 8:29 am
by Darko
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

Posted: Mon Apr 16, 2007 7:28 am
by sjn
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

Posted: Mon Apr 16, 2007 7:56 am
by rio
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.

Posted: Mon Apr 16, 2007 8:43 am
by sjn
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!

Posted: Mon May 07, 2007 8:33 am
by hamedv
why m is 30.
m most be 80

Re: 785 - Grid Colouring

Posted: Fri Oct 24, 2008 10:43 pm
by x140l31
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';
    }
}

Re: 785 - Grid Colouring

Posted: Wed Mar 10, 2010 8:59 am
by Obaida
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:

Re: 785 - Grid Colouring

Posted: Mon Apr 18, 2011 12:43 am
by Eather
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;
}

Re: 785 - Grid Colouring

Posted: Fri Jul 13, 2012 3:35 pm
by Scarecrow
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.

Re: 785 - Grid Colouring

Posted: Thu Oct 03, 2013 10:29 pm
by rosynirvana
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.

Re: 785 - Grid Colouring

Posted: Mon Mar 09, 2015 10:06 pm
by ehsanulbigboss
Got some hints :)

Re: 785 - Grid Colouring

Posted: Mon Jul 06, 2015 7:55 pm
by ocin_lr
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