Problem F


                           Problem F
                      Walking the matrix


Your  task  is  to create a program processing input  matrices
containing decimal digits to find the biggest possible  number
divisible  by three. Every matrix is a square and it  contains
25  decimal  digits  -  5 rows 5 digits  each.  The  resulting
numbers are constructed in the following way:
*    you  must start in the upper left corner of the matrix  -
 the  digit  in this corner is the leftmost, most  significant
 digit of the number being constructed,
*    you must end your route in the lower right corner of  the
 matrix  -  the  digit in this corner is the rightmost,  least
 significant digit of the number being constructed,
*    all other elements of the matrix may be visited only once
 or not visited at all,
*   the resulting number is constructed from left to right, by
 attaching consecutive digits to its right side,
*   there are only four possible moves: to the left, to the
right, up and down (provided you obey other rules, of course),
*   you must not pass the boundaries of the matrix; this means
 that if you for example reach the rightmost element in a  row
 you  cannot pass to the leftmost element of this row  in  one
 move.

Input
The input is as follows:
*    in  the first line there is the number of matrices in the
 input,
*    in the next lines there are rows of consecutive matrices,
 one row in a line, the digits are separated with spaces and/or
 tabs, the line ends with the end-of-line character,
*    the  last  line  of the input ends with  the  end-of-file
 character.

Output
The output should contain:
*    as many lines of answers as the number of matrices in the
 input,
*    every  line should contain one solution i.e. the  biggest
 possible number for the corresponding matrix or - if for  any
 reason it is not possible to construct one, the number 0,
*   all lines should end with the end-of-line character.
EXAMPLE

Input
For example, given the following input (three matrices):

3
1 2 3 4 5
6 7 8 9 0
1 2 3 4 5
6 7 8 9 0
1 2 3 4 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
3 3 3 3 3
1 1 1 1 1
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Output
We  obtain  the following answers (for each input  matrix  one
answer):

1672389450543872161234905
00033311300000000000031
0


Solution

                             Test

input        5
         1 2 3 4 5
         6 7 8 9 0
         1 2 3 4 5
         6 7 8 9 0
         1 2 3 4 5
         0 0 0 0 0
         0 0 0 0 0
         0 0 0 0 0
         3 3 3 3 3
         1 1 1 1 1
         5 5 5 5 5
         4 4 4 4 4
         3 3 3 3 3
         2 2 2 2 2
         1 1 1 1 1
         1 0 0 0 0
         0 0 0 0 0
         0 0 0 0 0
         0 0 0 0 0
         0 0 0 0 1
         2 3 9 8 9
         1 2 3 4 0
         0 9 0 2 1
         2 3 4 6 1
         0 9 8 1 2
         

output

         1672389450543872161234905
         00033311300000000000031
         5555544444333332222211111
         0
         23989043210939840211612


Listing

                            Listing

#include 
#include 

char szCTask[26], szSol[26], szBestSoFar[26];
unsigned short usVisited[25], usSolLen;

int div3(const char szNum[])    /* checks divisibility by 3 */
{
  unsigned uSum, uI;
  uSum = uI = 0;
  while(szNum[uI] != '\0')uSum += szNum[uI++]-'0';
  /* sum all digits */
  return(!(uSum % 3));
}
/* compares two strings/numbers */
int gt(const char szs1[], const char szs2[])
{
  unsigned uL1, uL2, uI;
  char szS1[26], szS2[26];
  /* remove all trailing zeroes */
  uL1 = 0; while(szs1[uL1]=='0')uL1++;
  strcpy(szS1,&szs1[uL1]);
  uL2 = 0; while(szs2[uL2]=='0')uL2++; /* as above */
  strcpy(szS2,&szs2[uL2]);
  uL1 = strlen(szS1);
  uL2 = strlen(szS2);
  if(uL1 != uL2)
    if(uL1 > uL2)return(1); /* longer is bigger */
    else return(0);         /* shorter is smaller */
  else
    /* compare digits left to right */
    for(uI = 0;szS1[uI]!='\0';uI++)
    {
      if(szS1[uI]>szS2[uI])return(1);
      if(szS1[uI] 4)
      if(usVisited[usI-5]==0)findSolution(usI-5); /* move up */
    if(usI < 20)
      if(usVisited[usI+5]==0)findSolution(usI+5); /*move down*/
  }
  usVisited[usI] = 0;
  szSol[--usSolLen]='\0';
}

void getTask(void)      /* reads task from console */
{
  unsigned short usCElem, usBuf;
  for(usCElem=0;usCElem<25;usCElem++)
  {
    scanf("%hu",&usBuf);
    szCTask[usCElem]=usBuf+'0';
    usVisited[usCElem] = 0;
  }
  szCTask[25]=szBestSoFar[0]='\0';
  usSolLen = 0;
}

int main (void)
{
  unsigned short usTasksNo, usCTask;
  scanf("%hu",&usTasksNo);
  for(usCTask=0;usCTask < usTasksNo;usCTask++)
  {
    getTask();
    findSolution(0);
    if(szBestSoFar[0]!='\0')puts(szBestSoFar);
    else puts("0");
  }
  return(0);
}


© zwir, wierzej, Mon Oct 28 23:01:26 MET DST 1996