Description

Write a program that simulates a mouse in a maze. The program must count all the number of paths the mouse can take from the starting point to the final point.

The maze type is shown in following figure:

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

it consists of S (starting point), #(wall), $(road) and F (final point). The mouse can move in the four directions: up, down, left, and right. Note that each $(road) can only be passed for one time.

The above case has 4 different paths from S to F as follows:

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 all the number of paths 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

(Partial Judge) Given a pointer integer array **ptr with size N, and an integer array *array with size (N+1)*N/2. Please use malloc function to allocate memory to **ptr and *array. The *array is an ascending sequence of number. Each pointer in array **ptr shall point to one element of *array where ptr[0] should point to array[0] and other ptr[i] should point to array[(i+1)*i/2] for all 0 < i < N.

For example, when n = 5, the size of **ptr will be 5, and the size of *array will be 15. The first pointer of **ptr is *ptr[0] which points to array[0], and the second pointer of **ptr is *ptr[1] which points to array[1], and the third pointer of **ptr is *ptr[2] which points to array[3], and the forth pointer of **ptr is *ptr[3] which points to array[6].

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" #pragma warning( disable : 4996 ) int main() { int *array; int **ptr; int N; int offset; scanf("%d %d",&N, &offset); malloc_array(&array, (1+N)*N/2); ptr = malloc_ptr(N); int i; for(i = 0; i < (1+N)*N/2; i++){ array[i] = i; } pointer_ptr_to_array(array,ptr,N); for(i = 0; i < N; i++){ printf("%d\n",*(ptr[i])+offset); } free(ptr); free(array); return 0; }

function.h

int** malloc_ptr(int array_size); void malloc_array(int **array, int array_size); void pointer_ptr_to_array(int *array, int **ptr,int N);

Input

The first line is size of **ptr

The second line is offset

0 <= offset < size <3000

Output

Print each pointer of *(*ptr + offset)

Note that you need to print a newline character ‘\n’ after each number, that is, just one number will be shown in each line of the output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12499.c

Partial Judge Header

12499.h

Tags

Discuss