Description

Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.

The maze type is shown in following figure:

S$###
$$#$$
$$$##
##$$F

it consists of S (starting point), #(walls), $(road) and F (final point).

In above case, it needs 7 steps from S to F as following figure,

S$###
$$#$$
$$$##
##$$F

and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.

If there is no way from S to F, then print -1.

Input

The first line has an integer N(1<=N<=10^6), which means the number of test cases.

For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.

The following R lines, each containing C characters, specify the elements of the maze.

Output

Print out the least steps for each case, and there is a new line character at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One day, Panda gives an unreadable message M and a special number P.
You need to decode the message M by the number P

The message M is composed of several pairs of number and word xi, wi.
Each number xi must be followed by its corresponding word wi which length is greater than 0.
For example: 1A3B2C, 0Hello3World are valid, while 1A2B3, ABC123, ABC are not.

Let re-order function f(x) = x mod P
Then f(xi) represents the word order of wi.
For f(xi) < f(xj), wi appears before wj after decode.
For the words have the same order f(xi) = f(xj), concat these words in the appearing order in M and regard the concated string as a single word.

Given M and P, please decode the message M by the rule above and output the number of words in result.
!! This is a partial judge problem !!

 

Explaintation of Sample I/O

Sample 1:
M =1is5message3this, P = 3
f(xi), wi : (1,is), (2,message), (0,this).
The decoded message is this is message which has 3 words.

Sample 2: with same index
M = 1Hel4lo7World, P = 3
f(xi),wi: (1,Hel), (1,lo), (1,World).
The decoded message is HelloWorld which has 1 words.

 

Partial Code

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "function.h"

#define maxn 1000
#define maxl 1000

int P;
char M[1000010];

int main() {
    int n = 0;
    char Table[maxn][maxl+1]; // +1 for null char
    char *ptr[maxn];

    for (int i = 0; i < maxn; i++) {
        for(int j=0; j < maxl + 1; j++)
            Table[i][j] = '\0';
        ptr[i] = &Table[i][0];
    }

    scanf("%d", &P);
    scanf("%s", M);

    solver(ptr, &n, P, M);
    
    int cnt = 0;
    printf("%d\n", n); // the # of words
    for(int i=0; i<P; i++){
        if( strlen( Table[i] ) != 0 ){
            // if the position is non-empty.
            if( cnt < n-1 )
                printf("%s ", Table[i]);
            else
                printf("%s\n", Table[i]);
            cnt++;
        }
    }
    return 0;
}

function.h

#ifndef FUNCTION_H
#define FUNCTION_H

void solver(char **ptr, int *n, int P, char *M);
#endif

 

What you need to do in this problem

1. Download "13022.c" file, and rename as "main.c"
2. Download "13022.h" file, and rename as "function.h"
3. Trace the code in "main.c"
4. Implement the solver function in "function.c"
5. Compile your project in your local IDE
6. Submit your "function.c" to OJ

 

In your solver function, based on P and *M, you should use **ptr and *n to update the values of Table[][] and n in the main function as required. For example, for Sample 1 above, your Table[][] and n should be:

Hints for testcases

• For the 1~3-th testcases: f(xi) ≠ f(xj) for all i, j
• For the 4~6-th testcases: f(xi) = f(xj) for some i, j

Input

There’re 2 lines for input.
The first lines contains P.
The second lines contains M

It’s guaranteed that:

• 1 ≤ |M| ≤ 10⁶
• 1 ≤ P ≤ 1000
• xi ≥ 0
• The # of (xi,wi) pairs ≤ 1000
• The maximum length of each word after decoding ≤ 1000

Output

Output the number of words in decoded message on the first line.
and print decoded message on the second line, where the words are separated by white space.

Remember ‘\n’ on the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13022.c

Partial Judge Header

13022.h

Discuss