Description

Now you are in the World of Tanks !!!

 

Your mission is to follow the instructions and pick the coins : )

You will get a map of the world like this:

               

 

 is your tank with size 3x3 (xox is the head of the tank), and $ represents a coin, # represents the wall, ^ represents the hill.

If your tank (3x3 body) is above the $, you will pick it up ($ can't be counted again). If # or ^ is in front of the tank (in front of the xox, tank's front part), you can not move. Coins' position does not overlap initial tank's position.

The tank has four forward directions (South, East, North, West). Its direction is where xox heads. Notice that the upper of the map is the North, and the initial direction of the tank is not always North.

And you will receive a sequence of instructions, which contains F (takes a step along the tank's head direction), R (tank's head turns right), and L (tank's head turns left). Instructions like R and L only change tank's head direction, and don't affect the tank's position (would not cause moving). 

Your mission is to receive the instructions and drives the tanks in order to collect coins, and report the amount of coins you get in the end.

Notice: The sample input in the below seems not aligned because the size of each character is not identical. You can see the map above (it is the same as sample input) if you want to see clearly.

 

P.S: Kind professor HT Chen asks TA to give students a code template. You can follow codes below to just finish 5 functions above the main(), and you don't need to change any content in the main(). Or you can decide to write whole codes by yourself, it's up to you :)

 

#include <stdio.h>
#include <string.h>

#define EAST 0
#define SOUTH 1
#define WEST 2
#define NORTH 3

char map[100][100];
char actions[100]={};
int coin_amount = 0;

// tank's initial direction
char init_dir;
// tank's direction now
int dir_now;
// tank's center x and y
int center_x, center_y;

void decide_initial_direction()
{
    /// Decide tank's initial direction
    /// Using init_dir
    /// To determine dir_now

 

}

void take_a_step()
{
    if (dir_now == NORTH){
        /// Detect wall first
        if ( ??? ){

        }
        /// And then detect hill
        else if (( ??? )) {

        }
        /// If there is no obstacle, take a step
        else {

        }
    }
    else if (dir_now == SOUTH){

    }
    else if (dir_now == EAST){

    }
    else if (dir_now == WEST){

    }
}

void pick_the_coins()
{
    int j, k;
    for (j = center_x - 1; j <= center_x + 1; j++){
        for (k = center_y - 1; k <= center_y + 1; k++){
            /// determine whether there are coins under the tank

 

        }
    }
}

void turn_right()
{
    /// Change direction depending on dir_now
}

 

void turn_left()
{
    /// Change direction depending on dir_now
}

int main()
{
    int i, j, k, rows, cols;
    int actions_number;
    int component = 0;

    /// Raed problem's input
    scanf("%d %d %d %c", &rows, &cols, &actions_number, &init_dir);
    while (getchar() != '\n');
    for (i = 0; i < actions_number; i++){
        scanf("%c", &actions[i]);
    }

    /// Read map
    for (i = 1; i <= rows; i++){
        while (getchar() != '\n');
        for (j = 1; j <= cols; j++){
            scanf("%c", &map[i][j]);
            /// Find tank's center x and y
            if (((map[i][j]) == 'x') || ((map[i][j]) == 'o') || ((map[i][j]) == 'O')){
                component++;
                if (component == 5){
                    center_x = i;
                    center_y = j;
                }
            }
        }
    }

    decide_initial_direction();

    for (i = 0; i < actions_number; i++){
        if (actions[i] == 'F'){
            take_a_step();
            pick_the_coins();
        }
        else{
            if (actions[i] == 'R'){
                turn_right();
            }
            if (actions[i] == 'L'){
                turn_left();
            }
        }
    }

    printf("%d\n", coin_amount);

    return 0;
}

 

 

 

Input

The first line of the input contains four things: 

1. The rows of the map (0 < rows < 100)

2. The columns of the map (0 < cols < 100)

3. The total length of instructions (0 < instructions's length < 100)

4. The initial tank's direction (N, E, S, W)

The second line is the content of instructions.

For the next lines, they illustrate the map.

Output

The number of coins you get. (printf "\n" in the end)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Our aspiring and naughty professor HT Chen is so happy to see you guys having solved his "exquisite substring" problem !!

But he found that there was also another special attribute of strings he wrote down. 

He found that for any 2 string consisted by '0'to '9' , 'a' to 'z' and 'A' to 'Z', we can find a common longest substring (CLS) of them, which is belongs to the both sequences, continue, left to right, as long as possible and the length of substring might be 1.

For instance, the CLS of "aabbccdd" and "bbaaccdd" is "ccdd".

HT was wondering the length of the CLS for each pair string he wrote on the paper. Counting them by hand will be a dreadful work, so he decided to give it as one of the questions of your midterm. HT would be happy if you both getting your midterm score and solving his problem.

Input

There are multiple lines in each testcase. Every two lines contains a pair of strings that HT wrote on the paper.

The input file is ended by 'EOF'.

It is guaranteed that (s is a arbitrary string in corresponding testcase):

• At most 10 pairs of lines in each testcase.
• testcase #1 ~ #5 : 1 ≤ | s | ≤ 50
• testcase #6 ~ #8 : 50 ≤ | s | ≤ 500
• testcase #9 ~ #10 : 500 ≤ | s | ≤ 1000

For the last 2 testcases, try to recall the method for the bonus testcase of pE we had discussed on Monday.

Or you can try to complete the other 2 questions first then focusing on the 9th & 10th testcases.

 

Output

For each string pair si, please output a line contains one integer representing the length of CLS in si.

If there is not a CLS, please output 0.

(i.e. Please print '\n' after each answer.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

     After the "common longest substring" problem, it occurred to professor HT Chen that he forgot to set the third problem. It's difficult for HT to give a proper problem at this midterm. Suddenly, he sees a map on the table, and a idea appear in his mind.

     There are some cities on the map,  some roads connecting some of them. And, there are only one road between two connected cities, of course, all of the roads are undirected. The figure below is an example of the problem instance. City 1, 6, 2 are connected, and 4, 5 are also connected by the other route. City 3 isn't connected with any other city. Now, HT hopes you guys to find that if there is a route from one city to another one.

Hint. You can use 2-D array to record the road between the city, and use some characters to indicate where  the road is. For example, you can use array to store the data, and just modify the data in array then you can get the answer.

 

 

Hint. You can judge that two cities is connected to the same city or not. If so, these three cities may connected together.

Hint. Mutiple for loop might be used in this problem.

 

You can see the sample code for all the hint. 

#include <stdio.h> #include <stdlib.h> int main() { int i, j, k; int city, con; int a, b; int Map[?][?]; /* You must initialize something here! */ scanf("%d%d", &city, &con); for(i=1; i<=con; i++){ scanf("%d %d", &a, &b); // Store the data here! } // Remember to modify the ??? in the for loop! for(k=1; k<= ??? ; k++){ for(i=1; i<= ??? ; i++){ // Somrthing might be writed here or not! for(j=1; j<= ??? ; j++){ // The most important judge might be writed here! } } } int test; scanf("%d", &test); for(i=0; i<test; i++){ scanf("%d %d", &a, &b); // Write your output type here! } return 0; }

Input

The first element (called C) of first line  is the how many cities on the map. The second element  (called N) of first line is the number of road on the map. Each of the next N lines contains two numbers A and B. That means the city A and the city B are connected by one road. And after the first line and N lines, it will be one line that only contains one number T. T is the number of the problem that Jason want to know. So, after T, the next T lines represents the problem. Each of T lines include two numbers X and Y, and you need to print the connection is between  city X and city Y or not.

In the end, It is guaranteed that :

•  0 <=  C  <=  1000
•  0 <=  N  <=  C²
•  0 <=  T  <=  C²

 

Output

You need to print the connection is between  city X and city Y or not. And you need to print '\n' after each answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss