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

The kingdom of far worse is in trouble.

The enemies are going to attack kingdom of far worse.

 

The enemies have map of kingdom of far worse. The map shows that there are exactly some cities.

They are planning to isolate some cities of kingdom of far worse and their method is bomb some roads.

 

For example, there is a road between city 2 and city 3.

If the position of a bomb is (2, 3), the road from city 2 to city 3 will be destroyed by the bomb but there is still a road from 3 to 2.

 

The king of kingdom of far worse request you to write a program to show that which city does NOT have road can leave or enter it.

 

Note:

Below is a real map and its representation of 2-D array. Left-up is (1, 1).

 

For example of left part.

(1, 4) is 1, means there is a road from 1 to 4.

(4, 3) is 1, means there is a road from 4 to 3

(1, 2).is 0, means there is NO road from 1 to 2.

Input

One number N, N is the number of cities. 2 <= N <= 50

Following is a 2-D array map with N columns and N rows.

One number B, B is the number of bombs. 1 <= B <= N²

Following is B lines, each line is the position of bomb.

Output

Which city does NOT have road can leave or enter it.

The order of number is increasing. Each number is printed by format "%d\n" 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a matrix A (you can consider it as a 2-D array), print out transpose of A.

Note: Try to use dynamic memory management to finish this problem.

main.c

#include <stdio.h>

#include "function.h"


int main(void) {


  int **mat;

  int m, n, i;


  scanf("%d %d", &m, &n);


  mat = allocateMat(m, n);

  readInput(mat, m, n);

  printResult(mat, m, n);


  // Be sure to release acquired memory space

  for(i=0; i<m; i++)
    free(mat[i]);
  free(mat);

  return 0;

}

function.h

#ifndef FUNCTION_H

#define FUNCTION_H


int** allocateMat(int, int);

void readInput(int**, int, int);

void printResult(int**, int, int);


#endif

Input

First line has two integers, indicates A is M rows by N columns. Next M lines are the content of A, each line has N integers.

Output

N lines, each line contains M integers. Values are separated by a blank. There’s a blank and a newline at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10900.c

Partial Judge Header

10900.h

Tags

Discuss

Description

printf() and  scanf() format

printf("%d", n);
 

FORMAT  ARGUMENT TYPE

%d, %i  int           decimal

%u      unsigned int

%x      unsigned int  hexadecimal

%#x     unsigned int  hexadecimal with prefix 0x

%f      double  

%Lf     long double

%e, %E  double      scientific notation

%c      int         to print a character

%s      char *      string (character array ended with '\0')

%p      void *      print memory address

%g, %G  double      %f or %e depending on the length

scanf("%d", &n);
 

FORMAT  ARGUMENT TYPE

%d      int *       &n, store the input integer in n

%ld     long *

%lld    long long *

%u      unsigned int *

%f      float *     read float

%lf     double *    read double

%Lf     long double *   read long double

%c      char *      read 3 characters %3c

%s      char *      read a string until whitespace

%n      int *       with %s, to get string length

                   char a[100]; int len;
                 scanf("%s%n", a, &len);
                 len will have the string length

Frequently used functions

To create a 5-by-5 two-dimensional array, we need to write

int a[5][5];

 

It will be indexed as follows:

 

a[0][0]	a[0][1]	a[0][2]	a[0][3]	a[0][4]
a[1][0]	a[1][1]	a[1][2]	a[1][3]	a[1][4]
a[2][0]	a[2][1]	a[2][2]	a[2][3]	a[2][4]
a[3][0]	a[3][1]	a[3][2]	a[3][3]	a[3][4]
a[4][0]	a[4][1]	a[4][2]	a[4][3]	a[4][4]

 

 

How to read the following data?
1 2 3 4 5 e
#include <stdio.h>
int main(void)
{
    int x;
    while (scanf("%d", &x) == 1) {  
     printf("x=%d\n", x);
    }
    return 0;
}

How to read the following data?

2

L 5 2
D 5 3

#include <stdio.h>

int main(void)

{

   char ch;
   int i, n, row, col;

   scanf("%d", &n);

   for (i=0; i<n; i++) {

      while(getchar()!='\n');

      scanf("%c%d%d", &ch, &row, &col);

   }

   return 0;

}

Using for loops to print a two-dimensional array

   for(i = 0; i < row; i++) {
      for (j = 0; j < col; j++) {
         printf("%5d", A[i][j]);
      }
      printf("\n");
   } 

How to avoid common errors and how to debug for OJ

1. Put the arrays in the 'global' area. Set their size bigger than required. Avoid using variable-length arrays (e.g. int arr[n];). Keep the array size fix (e.g., int arr[1000];).

2. After writing the code for reading input data, you may print out the data to check if your code reads them correctly. Do not proceed to write subsequent code before you confirm that.

3. If your program crashes, usually it is caused by memory related errors. Check the ranges of for-loops to see if your code attempts to read or write the elements out of the arrays’ boundary.

 

 

#include <string.h>

strstr(str1,str2)

return a pointer to the first occurrence in str1 of the entire sequence of characters specified in str2, or a null pointer if the sequence is not present in str1.

 

strcmp(str1,str2)  

Compare two strings.

return

<0	if the first character that does not match has a lower value in ptr1 than in ptr2
0	if the contents of both strings are equal
>0	if the first character that does not match has a greater value in ptr1 than in ptr2

 

strncmp(str1,str2,num)   

Compares up to num characters of the C string str1 to those of the C string str2

return

<0	if the first character that does not match has a lower value in str1 than in str2
0	if the contents of both strings are equal
>0	if the first character that does not match has a greater value in str1 than in str2

 

#include <stdlib.h>

malloc(size)

return a pointer to the memory block allocated by the function.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss