Bee Bob is in a beehive with a size of M×N (see the figure below), where each cell of the beehive contains a letter (uppercase or lowercase English alphabet).
Bob starts at the bottom left corner of the beehive, and the directions of movement are defined as follows:
- 0 means moving diagonally to the right and up.
- 1 means moving to the right.
- 2 means moving diagonally downwards to the right.
- 3 means moving diagonally downwards to the left.
- 4 means moving to the left.
- 5 means moving to the upper left.
Please input the direction of each step, and output the representative letter of each grid passed through, as well as the number of distinct characters passed through (case-sensitive). If you encounter a wall during movement, the action will stop in place.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains three integers M, N, K (1 <= M, N <= 20, 1 <= K <= 100), indicating that the size of the hive is M*N, and Bob's walking path consists of K steps. The next M lines each contain N letters (lowercase and uppercase English letters), representing the state of the hive. The last line contains K integers, indicating the direction of Bob's movement path. | The output consists of two parts (each on one line): 1. A string composed of the letters represented by each grid that Bob passes through in each step. 2. The number of distinct characters encountered (uppercase and lowercase are considered distinct), represented as an integer. |
| 2 4 5 TyuI ABaB 0 1 2 3 0 | Tyaau 4 |
| 4 6 11 rMmnis LRveEX ZexDoc HAdbHA 0 1 5 1 1 0 3 0 0 1 0 | ZeLRvmvmmnn 7 |
Thought Process
The complexity of this problem lies in the fact that the structure of the hive is hexagonal, but the input is collected in a square format.
However, we can understand it as:
- When moving to the upper right, the changes in the values of x and y are (0, -1).
- When moving to the right, the changes in the values of x and y are (1, 0).
- When moving to the bottom-right, the changes in the values of x and y are (1, 1).
- When moving to the bottom-left, the changes in the values of x and y are (0, 1).
- When moving to the left, the changes in the values of x and y are (-1, 0).
- When moving to the left-up direction, the changes in the values of x and y are (-1, -1).
If you don't understand, you can try drawing Example 1's data to get an idea (as shown below). It will give you a rough understanding of the concept. It's important to note that you need to check if each movement will exceed the boundaries of the array. For counting the occurrences, you can use a Map to store the characters that have already appeared.
Sample Code－ZeroJudge M932: Observing Bees
#include <iostream>
#include <map>
#include <vector>
using namespace std;
pair<int, int>rtn (int a, int b)
{
pair<int, int>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
int main() {
int M, N, K;
cin >> M >> N >> K;
cin.ignore();
vector<string>v;
for (int i = 0; i<M; i++)
{
string tmp;
getline(cin, tmp);
v.push_back(tmp);
}
int x = 0, y = M-1;
map<int, pair<int, int>>MAP;
MAP[0] = rtn(0, -1);
MAP[1] = rtn(1, 0);
MAP[2] = rtn(1, 1);
MAP[3] = rtn(0, 1);
MAP[4] = rtn(-1, 0);
MAP[5] = rtn(-1, -1);
map<char, int>appear;
int ans = 0;
for (int i = 0; i<K; i++)
{
int tmp;
cin >> tmp;
int xx = x + MAP[tmp].first, yy = y + MAP[tmp].second;
//cout << xx << " " << yy;
if (xx >= 0 && xx < N && yy >= 0 && yy < M)
{
x = xx;
y = yy;
char ch = v[y][x];
if (isalpha(ch))
{
cout << ch;
if (appear[ch] == 0) ans++;
appear[ch]++;
}
}
else
{
char ch = v[y][x];
if (isalpha(ch))
{
cout << ch;
if (appear[ch] == 0) ans++;
appear[ch]++;
}
}
}
cout << "\n" << ans << "\n";
}
//ZeroJudge M932
//Dr. SeanXD