Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Grid's paths, River crossing pawn, and avoiding Knight's move, start to end count

Revision en1, by yawn_lento, 2026-07-21 04:51:02

// my attemt using Monte Carlo, effective when the number is small, but will resulting in RE when dealing with larger numbers

include

include

include

using namespace std; int rand01() { return rand() % 2; } struct point { int x, y; }; int distance(point A, point B) { return (A.x — B.x) * (A.x — B.x) + (A.y — B.y) * (A.y — B.y); } bool cmp(point m, point n) { return (m.x == n.x && m.y == n.y); } int main() { srand(time(0)); point horse, end; static point path[399][39]; cin >> end.x >> end.y >> horse.x >> horse.y; point temp; int valid = 0; int fork; int flag = 0; int count = 0; int attempt = 0; while (attempt < 10000) { temp.x = temp.y = 0; int step = 0; while (temp.x <= end.x && temp.y <= end.y && !cmp(temp, end)) { fork = rand01(); int tempx = temp.x, tempy = temp.y; if (temp.x < end.x && temp.y < end.y) { temp.x = temp.x + fork, temp.y = temp.y + 1 — fork; } else if (temp.x == end.x && temp.y < end.y) temp.y++; else temp.x++; if (distance(temp, horse) != 5 && !cmp(temp, horse)) { path[count][step] = temp; step++; } else { flag = 999; break; } } for (int i = 0; i < count; i++) { for (int j = 0; j < step; j++) { if (cmp(path[count][j], path[i][j])) flag++; } if (flag < step) flag = 0; } if (flag < end.x + end.y — 1 && cmp(temp, end)) {

       valid++;
       count++;
    }
    flag = 0;
    attempt++;
}
cout << valid << endl;

} //suggestions :using DP will be better

Tags monte carlo, grid paths, start to end

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English yawn_lento 2026-07-22 05:33:52 33 Tiny change: 'introduced. However,' -> 'introduced(though still not very effective). However,'
en8 English yawn_lento 2026-07-22 05:23:58 970
en7 English yawn_lento 2026-07-21 05:10:51 12
en6 English yawn_lento 2026-07-21 05:09:09 82
en5 English yawn_lento 2026-07-21 05:05:33 1583
en4 English yawn_lento 2026-07-21 05:01:28 42
en3 English yawn_lento 2026-07-21 04:55:47 22
en2 English yawn_lento 2026-07-21 04:53:13 26
en1 English yawn_lento 2026-07-21 04:51:02 1725 Initial revision (published)