علی کوچولو یک جدول $5\times 5$ دارد. هر یک از خانه‌های جدول به شکل یک آکواریوم سر باز است که می‌تواند پر ا ز آب یا خالی باشد.

یک ماهی در خانه‌ی بالا چپ جدول علی گیر افتاده است و می‌خواهد به خانه‌ی پایین راست (مقصدش) برود. می‌دانیم ماهی از یک خانه تنها می‌تواند به خانه‌ی مجاور سمت راست یا خانه‌ی مجاور پایینی بپرد؛ آن هم در صورتی که آن خانه پر از آب باشد (ماهی‌ها در خاک می‌میرند!). واضح است که همواره طول مسیر حرکت ماهی دقیقا ۸ پرش خواهد بود.

در ابتدای کار تنها مبدا و مقصد ماهی پر از آب هستند. علی می‌خواهد تعدادی از ۲۳ خانه‌ی دیگر جدول را انتخاب کرده و آن‌ها را پر از آب کند، به طوری که دقیقا یک مسیر پر آب برای حرکت ماهی از مبدا به مقصد (از هر خانه به پایین راست) وجود داشته باشد.

دقت کنید که علی اجازه دارد خانه‌هایی که در مسیر نیستند را هم پر کند؛ منتهی پر کردن این خانه‌ها نباید مسیر جدیدی برای رفتن از مبدا به مقصد برای ماهی بسازد. دو مسیر را متفاوت می‌گوییم اگر در حداقل یک خانه متفاوت باشند.

اگر تعداد راه‌های انجام این کار را $S$ بگیریم؛ باقی‌مانده‌ی $S$ بر $\Delta$ چند است؟

‎
 
 
 
#include <iostream> 
#include <vector> 
using namespace std; 
 
vector<int> path; 
 
int numones(int x) { 
  int c = 0; 
  for (; x > 0; x/= 2) 
    c += (x % 2); 
  return c; 
} 
 
int mask; 
#define cell(x,y) ((mask >> (x*5+y)) & 1) 
 
int main() { 
  for (int i=0; i<(1<<8); i++) 
    if (numones(i) == 4) 
      path.push_back(i); 
 
  int ans = 0; 
  for (mask = 0; mask <(1<<25); mask++) { 
    if (cell(0,0) == 0 || cell(4,4) == 0) continue; 
 
    int c = 0; 
    for (int k=0; k<(int)path.size(); k++) { 
      int curx = 0, cury = 0; 
      for (int j=0; j<8; j++) { 
        if ((path[k] >> j) & 1) curx++; else cury++; 
        if (cell(curx,cury) == 0) goto nextpath; 
      } 
      c++; 
      nextpath: ; 
   } 
   ans += (c == 1); 
  }  
 
  cout << ans << endl; 
 
  return 0; 
}

• سوال بعد
• سوال قبل