785 - Grid Colouring

[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

[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

[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

[rio]

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]

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]

why m is 30.
m most be 80

[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';
    }
}

[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.

[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;
}

[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.

[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.

[ehsanulbigboss]

Got some hints

[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