cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2010 · MediumBFS with state masks

Non-Euclidean Castle

National Olympiad — National round

Submission name: castle.cpp

Solve in Editor →

Problem summary

Start at E on a grid, visit every P, and finish at X. A move up, down, left, or right costs one minute. Both dimensions wrap: crossing a boundary enters the opposite edge in the same row or column. Walls (#) remain impassable, including across a wrap. You may cross X before visiting all P cells. Find the shortest total time, or −1 when impossible.

Input

N M, then N rows of M characters from E, X, P, . and #.

Output

Minimum minutes, or −1.

Constraints

1 ≤ N,M ≤ 50; at most 5 P cells.

Worked example

An independently prepared example for this explanation.

Input

1 4
EP.X

Output

3

Solution analysis

  1. Give each P a bit.
  2. BFS over (cell, visited-P mask); set a bit when entering its cell.
  3. Wrap neighbour coordinates modulo the grid dimensions. Accept only X with the full mask.

Why it works

The state contains all history that affects success. Its edges correspond exactly to legal one-minute moves, so BFS finds the minimum feasible arrival time.

Complexity: O(NM·2^p) time and space, p≤5.

Watch out. Do not stop at an exit with an incomplete mask or forget toroidal movement.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: The state contains all history that affects success. Its edges correspond exactly to legal
// one-minute moves, so BFS finds the minimum feasible arrival time.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<string>a(n);
    for(auto&s:a){
        cin>>s;
    }
    int s=0,f=0,p=0;
    vector<int>bit(n*m,-1);
    for(int r=0;r<n;r++){
        for(int c=0;c<m;c++){
            int v=r*m+c;
            if(a[r][c]=='E'){
                s=v;
            }
            if(a[r][c]=='X'){
                f=v;
            }
            if(a[r][c]=='P'){
                bit[v]=p++;
            }
        }
    }
    int masks=1<<p;
    vector<int>d(n*m*masks,-1);
    queue<pair<int,int>>q;
    q.push({s,0});
    d[s*masks]=0;
    int dr[]={-1,1,0,0},dc[]={0,0,-1,1};
    while(!q.empty()){
        auto[v,mask]=q.front();
        q.pop();
        int cur=d[v*masks+mask];
        if(v==f&&mask==masks-1){
            cout<<cur<<'\n';
            return 0;
        }
        for(int k=0;k<4;k++){
            int r=(v/m+dr[k]+n)%n,c=(v%m+dc[k]+m)%m;
            if(a[r][c]=='#'){
                continue;
            }
            int u=r*m+c,next=mask;
            if(bit[u]>=0){
                next|=1<<bit[u];
            }
            int state=u*masks+next;
            if(d[state]<0){
                d[state]=cur+1;
                q.push({u,next});
            }
        }
    }
    cout<<-1<<'\n';
}

Source: Arena Olimpiici ↗