## 125 - Numbering Ways - WA

Moderator: Board moderators

### 125 - Numbering Ways - WA

Hello, guys, I need your help in problem 125. My algorithm seems to be correct and it gives right answers to all inputs known to me, but it still gets WA.

Code: Select all
`#include <sys/types.h>#include <sys/stat.h>#include <fcntl.h>#include <stdio.h>#include <stdlib.h>#define SIZE 35               int main() {  int n, cities, step, i, j, k, c, count, curNeighbour, case_no;  int graph_matrix[SIZE][SIZE][SIZE], sum_matrix[SIZE][SIZE];  int neighbours [SIZE][SIZE];  int n_counter [SIZE];  int cycled_vertices[SIZE], good_vertices[SIZE];  int cycled_vertices_num, good_vertices_num;    case_no = -1;  while (1) {     if (scanf ("%d", &n) == 1) {                case_no++;                if (n == 0) {           printf ("matrix for city %d\n", case_no);           continue;        };                for (i=0; i<30; i++) {            n_counter[i] = 0;            for (j=0; j<30; j++) {                graph_matrix [0][i][j] = 0;                 neighbours[i][j] = -1;            }             }                 cities = 0;        for (k=0; k<n; k++) {            scanf ("%d %d", &i, &j);            if (i>cities)               cities = i;            if (j>cities)               cities = j;                        graph_matrix[0][i][j] = 1;            neighbours[i][ n_counter[i] ] = j;            n_counter[i]++;        }        cities++;                /* Iterative DP */        step = 1;        for (k=0; k<cities-1; k++) {            for (i=0; i<cities; i++)                for (j=0; j<cities; j++) {                     count = 0;                     curNeighbour = 0;                     while (neighbours[i][curNeighbour] > -1) {                          count += graph_matrix [step-1][ neighbours[i][curNeighbour] ][j];                          curNeighbour++;                      }                     graph_matrix[step][i][j] = count;                }                        step++;        }                 for (i=0; i<cities; i++)            for (j=0; j<cities; j++) {                count = 0;                for (k=0; k<cities; k++)                    count += graph_matrix[k][i][j];                sum_matrix[i][j] = count;                }                /* cycle detection */        cycled_vertices_num = 0;        good_vertices_num = 0;        for (i=0; i<cities; i++) {            if (sum_matrix[i][i]>0) {               cycled_vertices[cycled_vertices_num] = i;               cycled_vertices_num++;                                 } else {               good_vertices[good_vertices_num] = i;               good_vertices_num++;                                  }        }                /*  replacing all values for accessible vertices of cycled vertices with -1 */        for (i=0; i<cycled_vertices_num; i++) {            k = cycled_vertices[i];            for (j=0; j<cities; j++)                if (sum_matrix[k][j]>0)                   sum_matrix[k][j] = -1;           }                /* scanning good vertices, if good vertex has a route to a cycled vertice, all accessible points for this cycled vertice           must be replaced with -1 in good vertex */        for (i=0; i<good_vertices_num; i++) {            k = good_vertices[i];            for (j=0; j<cities; j++) {                if (sum_matrix[k][j] > 0 && sum_matrix[j][j] < 0) {                   for (c=0; c<cities; c++)                       if (sum_matrix[j][c] < 0)                          sum_matrix[k][c] = -1;                                     }            }            }                printf ("matrix for city %d\n", case_no);        for (i=0; i<cities; i++) {            for (j=0; j<cities; j++) {                if (j != 0)                   printf(" ");                printf ("%d", sum_matrix[i][j]);            }            printf ("\n");            }                           } else       break;               }    return 0; }`

Maybe the problem lies in invalid input handling?
gosdep
New poster

Posts: 1
Joined: Wed Sep 16, 2009 7:13 am

### Who is online

Users browsing this forum: No registered users and 1 guest