XOR Yo'llar masalasini qaysi dasturlash tillarida yechish mumkin?

ALGOR platformasida ushbu masalani C++, C, Java, Python, JavaScript va PHP dasturlash tillarida onlayn yechish va tekshirish mumkin.

Masalalar 139 #140

~/algor $ cat masalalar/xor-yollar

XOR Yo'llar

I Muallif: Iqbolshoh Ilhomjonov

Qiyin 2000 ms 256 MB Urinishlar

Ulashish

Mavzular: Dinamik dasturlash

Olimpiada chempioni robot uchun maxsus labirint yaratdi.
Labirint $N \times M$ o'lchamli katakchalardan iborat panjara bo'lib, har bir $(i, j) katakda nomanfiy butun son C_{i, j}$ yozilgan.

Robot $(1, 1)$ katakdan boshlab harakat qiladi va faqat o'ngga $(i, j+1)$ yoki pastga $(i+1, j)$ qarab yurishi mumkin. Robotning maqsadi $(N, M)$ katakka yetib borishdir.

Yo'l davomida bosib o'tilgan barcha kataklardagi sonlarning bitwise XOR ($\oplus$) yig'indisi hisoblanadi.
Robotning har bir yo'li omadli hisoblanadi, agar yo'ldagi barcha sonlarning XOR yig'indisi berilgan sehrli X soniga teng bo'lsa!

Robot $(1, 1) dan (N, M)$ ga boradigan jami nechta har xil omadli yo'l mavjudligini aniqlang.

Kiruvchi ma'lumotlar

Birinchi qatorda uchta butun son: N, M va X ($1 \le N, M \le 20, N + M \le 22, 0 \le X \le 10^9$) kiritiladi.
Keyingi N ta qatorda M tadan butun son: $C_{i, j}$ ($0 \le C_{i, j} \le 10^9$) kiritiladi.

Chiquvchi ma'lumotlar

XOR yig'indisi X ga teng bo'lgan yo'llar sonini chiqaring.

Izoh

1-namuna:
3 3 11
2 1 5
7 10 0
12 6 4
Chiqish: 3

2-namuna:
1 1 5
5
Chiqish: 1

3-namuna:
2 2 0
1 2
3 4
Chiqish: 0

Misollar

Kirish #1

Chiqish #1

Kirish #2

1 1 5
5

Chiqish #2

Kirish #3

2 2 0
1 2
3 4

Chiqish #3

Yechim tahlili

Avval o'zingiz yechib ko'ring — tahlilni o'qish o'rganishga yordam beradi, lekin javobni tayyor beradi.

### Masala tahlili (Problem E) Panjarada $(1, 1) dan (N, M)$ ga yetib borish uchun har qanday yo'l aynan $(N-1) + (M-1) = N + M - 2$ ta qadamdan iborat. $N + M \le 22$ bo'lganligi uchun jami yo'llar soni ko'pi bilan $\binom{N+M-2}{N-1} \le \binom{20}{10} = 184,756$ ta bo'ladi. Bu miqdor juda kichik! Oddiy rekursiv qidiruv (DFS) orqali barcha yo'llarni tekshirib chiqish mumkin: ```cpp #include #include using namespace std; int n, m; long long target; long long grid[25][25]; long long ans = 0; void dfs(int r, int c, long long cur) { cur ^= grid[r][c]; if (r == n - 1 && c == m - 1) { if (cur == target) ans++; return; } if (r + 1 < n) dfs(r + 1, c, cur); if (c + 1 < m) dfs(r, c + 1, cur); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); if (cin >> n >> m >> target) { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> grid[i][j]; dfs(0, 0, 0); cout