मान लीजिए हमारे पास H पंक्तियों और W कॉलम वाला एक ग्रिड है। जहां प्रत्येक वर्ग साफ या गंदा है। हम इस ग्रिड में शून्य या अधिक साफ वर्गों पर लैंप रख सकते हैं। एक लैंप चार दिशाओं में से प्रत्येक में सेल को रोशन कर सकता है - ऊपर, नीचे, बाएं, और दाएं - ग्रिड के किनारे या पहली बार गंदे वर्ग तक पहुंचने से ठीक पहले तक (गंदा सेल रोशन नहीं होगा)। लैंप उस सेल को भी रोशन करेगा जिस पर वह रखा गया है। ग्रिड में यदि G[i, j] '.' है तो वह सेल साफ है और जब यह '#' है तो यह गंदा है। मान लें K साफ वर्गों की संख्या है। लैंप रखने के कुल 2^K तरीके हैं। मान लें कि, इन 2^K तरीकों में से प्रत्येक के लिए, एक या अधिक लैंप द्वारा रोशन सेल की संख्या की गणना की जाती है। हमें उन संख्याओं का योग 10^9 + 7 मॉड्यूलो ढूंढना है।
उदाहरण के लिए, यदि इनपुट है:
| . | . | # |
| # | . | . |
तो आउटपुट 52 होगा
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
m := 10^9 + 7 N = 2003 क्रम N x N के 2D ऐरे u, l, r, d परिभाषित करें, और N^2 तत्वों वाली एक सूची p। h := मैट्रिक्स की पंक्ति संख्या w := मैट्रिक्स की कॉलम संख्या tidy := 0 p[0] := 1 i := 1 से h * w तक, करें: p[i] := p[i - 1] * 2 mod m i := 0 से h-1 तक, करें: j := 0 से w-1 तक, करें: u[i, j] := i l[i, j] := j यदि i शून्येतर है, तो: u[i, j] := u[i - 1, j] यदि j शून्येतर है, तो: l[i, j] := l[i, j - 1] यदि matrix[i, j], '#' के बराबर है, तो: u[i, j] := i + 1 l[i, j] := j + 1 अन्यथा tidy बढ़ाएं i := h - 1 से 0 तक, करें: j := w - 1 से 0 तक, करें: d[i, j] := i r[i, j] := j यदि i < h - 1, तो: d[i, j] := d[i + 1, j] यदि j < w - 1, तो: r[i, j] := r[i, j + 1] यदि matrix[i, j], '#' के बराबर है, तो: d[i, j] := i - 1 r[i, j] := j - 1 cnt := 0 i := 0 से h-1 तक, करें: j := 0 से w-1 तक, करें: यदि matrix[i, j], '#' के बराबर है, तो: अगले पुनरावृत्ति पर जाएं src := d[i, j] + r[i, j] - u[i, j] - l[i, j] + 1 cnt := (cnt + (p[src] - 1) * p[tidy - src]) mod m cnt वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; const int m = 1e9 + 7, N = 2003; int u[N][N], l[N][N], r[N][N], d[N][N], p[N * N]; int solve(vector<vector<char>> matrix){ int h = matrix.size(); int w = matrix[0].size(); int tidy = 0; p[0] = 1; for (int i = 1; i <= h * w; ++i) p[i] = p[i - 1] * 2 % m; for (int i = 0; i < h; ++i){ for (int j = 0; j < w; ++j){ u[i][j] = i; l[i][j] = j; if (i) u[i][j] = u[i - 1][j]; if (j) l[i][j] = l[i][j - 1]; if (matrix[i][j] == '#'){ u[i][j] = i + 1; l[i][j] = j + 1; } else ++tidy; } } for (int i = h - 1; i >= 0; --i){ for (int j = w - 1; j >= 0; --j){ d[i][j] = i; r[i][j] = j; if (i < h - 1) d[i][j] = d[i + 1][j]; if (j < w - 1) r[i][j] = r[i][j + 1]; if (matrix[i][j] == '#'){ d[i][j] = i - 1; r[i][j] = j - 1; } } } int cnt = 0; for (int i = 0; i < h; ++i){ for (int j = 0; j < w; ++j){ if (matrix[i][j] == '#') continue; int src = d[i][j] + r[i][j] - u[i][j] - l[i][j] + 1; cnt = (cnt + (p[src] - 1) * p[tidy - src]) % m; } } return cnt; } int main(){ vector<vector<char>> matrix = { { '.', '.', '#' }, { '#', '.', '.' } }; cout << solve(matrix) << endl; } इनपुट
3, 2, { 1, 5, 9 }, { 2, 4, 2 } आउटपुट
52
