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 C2024 · MediumGrid Simulation

Deterministic Knight Walk

National Olympiad — Municipal round

Submission name: knight.cpp

Solve in Editor →

Problem summary

A chess knight starts at row i, column j of an n×m board. At each step it must move to an unvisited legal destination with the smallest row number, breaking ties by smallest column number. It stops when no such destination exists. Count visited cells, including the initial cell.

Input

n m i j.

Output

Number of visited cells.

Constraints

1 ≤ i ≤ n ≤ 10000; 1 ≤ j ≤ m ≤ 10000; stated time limit 0.1 seconds and memory limit 256 MB.

Worked example

An independently prepared example for this explanation.

Input

1 1 1 1

Output

1

Solution analysis

  1. Order the eight knight displacement pairs lexicographically by row displacement then column displacement.
  2. At every cell, take the first legal unvisited destination in this fixed order.
  3. Store visited cells as packed bits, keeping memory modest even for a 10000×10000 board.

Why it works

Adding the same current row and column preserves lexicographic ordering of displacements. Therefore the first eligible move is exactly the move required by the statement. Every iteration marks a new cell, so termination is guaranteed.

Complexity: O(nm) worst-case time, at most eight move checks per visited cell; O(nm) bits of storage.

Watch out. This is a deterministic walk, not a longest knight path problem. Include the start and never revisit cells.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: Adding the same current row and column preserves lexicographic ordering of displacements.
// Therefore the first eligible move is exactly the move required by the statement.
#include<iostream>
#include<vector>
#include<utility>
using namespace std;
int main(){
    int n,m,r,c;
    cin>>n>>m>>r>>c;
    --r;
    --c;
    vector<unsigned long long>seen(((long long)n*m+63)/64);
    int dr[8]={-2,-2,-1,-1,1,1,2,2},dc[8]={-1,1,-2,2,-2,2,-1,1};
    int ans=0;
    while(true){
        long long id=(long long)r*m+c;
        seen[id/64]|=1ULL<<(id%64);
        ans++;
        bool moved=false;
        for(int z=0;z<8;z++){
            int x=r+dr[z],y=c+dc[z];
            if(x<0||x>=n||y<0||y>=m){
                continue;
            }
            long long k=(long long)x*m+y;
            if(seen[k/64]>>(k%64)&1){
                continue;
            }
            r=x;
            c=y;
            moved=true;
            break;
        }
        if(!moved){
            break;
        }
    }
    cout<<ans<<'\n';
}

Source: Arena Olimpiici ↗