Description

Given a dictionary with n words, such as A1, A2, ..., An, and a string B for searching. If B is a substring of Ai, then Ai is one of the word that we want to search. Find out all the words we want to search.

Note that all the words in dictionary and the string B contain only uppercase or lowercase alphabets. And when searching, uppercase letters are considered the same as lowercase letters, for example, we can use 'the' to find 'THE'.

Input

The first line of the input is an integer n (0<n≦1000).

For the next n lines, each line contains a string Ai (0<length of Ai≦100) and a ‘\n’ at the end of the line.

The last line contains the string B (0<length of B≦10).

Output

Print out all the searched words in their original order in dictionary. Note that you NEED to print ‘\n’ at the end of all the words.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

Given the position of N cars and M barriers on a map, we have to list the valid moves of each car along 4 directions (i.e. right, down, left and up).

The width of a car must be 1, the length is between 2 and 9.

If the row of the tail of a car is the same as the row of the head, then the car is a horizontal car. Similarly, if the column of the tail of a car is the same as the column of the head, then the car is a vertical car.

Note that horizontal cars can only move horizontally, vertical cars can only move vertically.

A car must stop when it encounters a barriers (i.e. the character ‘#’ in the map).

For example, a map with 10 cars and 4 barriers is shown below:

Given the coordinate of car 2 is 1 3 1 6, it means car 2 occupies the position of (1,3) to (1,6) in the map. Car 2 can only move horizontally since the row of its tail and head are both 1.

The valid moves of car 2 is 1 0 1 0, which means it can move right 1 grid, can’t move down, can move left 1 grid and can’t move up.

 

Note that

1.      This problem involves three files.

• function.h: Function definition of list_moves.
• function.c: Function implementation of list_moves.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

Hint

function.h

#ifndef FUNCTION_H #define FUNCTION_H #define MAP_SIZE 9 #define MAX_CARS 10 #define SPACE '.' #define BARRIER '#' char map[MAP_SIZE][MAP_SIZE]; int cars[MAX_CARS][4]; void list_moves(int); #endif

main.c

#include <stdio.h> #include "function.h" int main(void) { int i,j,k; int num_cars,num_bar; int bar_row,bar_col; scanf("%d%d",&num_cars,&num_bar); //reset map for (i=0; i<MAP_SIZE; i++) { for (j=0; j<MAP_SIZE; j++) { map[i][j] = SPACE; } } //read coordinates of cars and put them on the map for (i=0; i<num_cars; i++) { scanf("%d%d%d%d", &cars[i][0], &cars[i][1], &cars[i][2], &cars[i][3]); for (j=cars[i][0]; j<=cars[i][2]; j++) { for (k=cars[i][1]; k<=cars[i][3]; k++) { map[j][k] = i+'0'; } } } //read coordinates of barriers and put them on the map for (i=0; i<num_bar; i++) { scanf("%d%d", &bar_row, &bar_col); map[bar_row][bar_col] = BARRIER; } list_moves(num_cars); return 0; }

 

Input

The first line has two integer N and M (1<=N,M<=10), which means the total number of cars and total number of barriers.

The following N lines are the coordinates of all cars.

Each line consists of 4 numbers. The first two numbers are the row and column of the head of the car. The other two numbers are the row and column of the tail of the car.

The following M lines are the coordinates of all barriers.

Each line consists of 2 numbers, which are the row and column of the barrier.

Output

Print out the valid moves of the cars in each line.

Each line consists of 4 number, the valid moves along right, down, left and up.

All of the numbers in the same line are separated by a space, and there is a '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10902.c

Partial Judge Header

10902.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