The problem number is 9328, which is Gold 1 problem according to solved.ac.

Let me explain how I solved this step by step.

Input

First, receiving and saving the map.

The map is consisted with five elements, and how I assigned them.

1. Floor .: 0
2. Wall *: -100
3. Locked Doors A: -1 ~ 26
4. Keys a: +1 ~ 26
5. Points $: +100

I could use sbyte for this, but for the sake of short coding, I used int.

StreamReader R = new(new BufferedStream(Console.OpenStandardInput()));
int T = int.Parse(R.ReadLine()); // test cases
L: // loop
var s = R.ReadLine().Split();
int H = int.Parse(s[0]), W = int.Parse(s[1]), i = 1, j;
var M = new int[H + 2, W + 2];
for(; i <= H; ++i)
{
    var t = R.ReadLine();
    for (j = 1; j <= W; ++j)
    {
        char c = t[j - 1];
        if (c == '.') continue;
        if (c == '*') M[i, j] = -99;
        else if (char.IsUpper(c)) M[i, j] = 'A' - c - 1;
        else if (char.IsLower(c)) M[i, j] = c - 'a' + 1;
        else M[i, j] = 99;
    } // -99 wall -A door 0 floor +a key +99 money
}
var K = new bool[27]; // key inventory
var q = R.ReadLine();
if (q != "0") foreach (var k in q) K[k - 'a' + 1] = true;

What’s up with those variable names

I must assure you that the way I code in problem solving is NOT the way I usually code.

However, for the reference, the naming scheme I use for problem solving is:

• Capital letter for const, readonly input, major variables including output
• Lower letter for local variables
• The alphabet is either specified by the problem, or the first letter of its function/type

BFS

var V = new bool[H + 2, W + 2]; // visited
Queue<int[]> Q = new(); Q.Enqueue(new int[] { 0, 0 }); // BFS queue
var D = new Stack<int[]>[27]; // doors
for (i = 1; i < 27; i++) D[i] = new();
int P = 0; // points: output

Now I add Queue of next position to check, for BFS. Then added array of Stacks where to store “encountered but locked doors found so far”. That’ll definitely cost memories, but in return we get time saves.

Finally, the points collected so far for the output.

Valid position checker

bool C(int u, int v)
{
    if (u < 0 || v < 0 || u > H + 1 || v > W + 1) return false;
    if (V[u, v]) return false;
    if (M[u, v] < 0)
    {
        if (M[u, v] < -50) return false; // wall
        if (K[-M[u, v]]) return true; // unlockable
        D[-M[u, v]].Push(new int[] { u, v }); return false; // pending door
    }
    return true;
}

The first line’s exception handler is obvious. I won’t tell you how many time I get IndexOutOfRange for screwing that.

Then visit check next, as this is BFS.

Now map checker, where I get to explain things.

I put keys and points in positive number for this reason, as I can use < 0 for initial check.

Then, if this is < -50 (equals to == -99 in this context but with one less characters), this is a wall so impenetrable.

If it’s not, then this is a door. The way I assigned allows that flipping negative naturally aligns with key inventory. And if the key is already present, can pass through.

If not, add that to the pending door stack for now. So how that will be used?

BFS itself

It is standard 2D BFS except collecting item part.

while (Q.Count > 0)
{
    var p = Q.Dequeue();
    int x = p[0], y = p[1];
    if (V[x, y]) continue;
    V[x, y] = true;
    if (M[x, y] > 0) // collect item
    {
        if (M[x, y] > 50) ++P; // $
        else // key
        {
            K[M[x, y]] = true;
            while (D[M[x, y]].Count > 0) Q.Enqueue(D[M[x, y]].Pop()); // add new doors
        }
    }
    if (C(x - 1, y)) Q.Enqueue(new int[] { x - 1, y });
    if (C(x + 1, y)) Q.Enqueue(new int[] { x + 1, y });
    if (C(x, y - 1)) Q.Enqueue(new int[] { x, y - 1 });
    if (C(x, y + 1)) Q.Enqueue(new int[] { x, y + 1 });
}

When Map is positive number, it’s an item.

If it’s > 50 (equal to == 99), it’s a point so add that.

If not, it’s a key so update the inventory. And if there’re unopened doors for that key, add them to the queue.

The reason I used Stack for this is, if there’re duplicate keys, the doors won’t be checked again as they left the Stack. (Queue would also work for this, but Enqueue and Dequeue is longer than Push and Pop)

I’ve just noticed that I cannot calculate the fastest route this way, even if I’m using BFS.

Hmm… If there’s an advanced problem which requires me to get that, I could probably add another Queue to store each important locations, and run a batch of BFS with slightly different behaviour.

Food for thought.

Output and next test case

Console.WriteLine(P);
if (--T > 0) goto L;

Now output P for this test case, and if there’re test cases left, go back to label L.

I use goto instead of while, because using while creates indents, and that costs 4 bytes for each line.

I don’t use goto in practice… that much. I believe there are rare cases that this actually improves readability (e.g. escaping loop stack), and I continue to use them for those.

The full source link