12
मैं स्थानीय प्रोग्रामिंग प्रतियोगिता से प्रोग्रामिंग समस्या की समीक्षा कर रहा हूं।प्रोग्रामिंग अभ्यास (फिटिंग पाइप) के लिए बैकट्रैकिंग समाधान
आप समस्या here (पीडीएफ) डाउनलोड कर सकते हैं। यह डच में है लेकिन चित्र इसे समझने में मदद करेंगे।
आपको कुछ पाइप और कुछ गायब धब्बे (प्रश्नचिह्न) के साथ इनपुट के रूप में एक एम * एम ग्रिड प्राप्त होता है। शेष पाइप को ग्रिड में रखा जाना चाहिए ताकि वे दूसरों के साथ जुड़ सकें।
प्रत्येक पाइप को एक पत्र के रूप में दर्शाया जाता है (पृष्ठ 2 पर चित्र देखें)। अक्षर 'ए' में मान 1 है, 'बी' का मान 2 है, ..
मैंने बैकट्रैकिंग के साथ इसे हल करने का प्रयास किया (यह अभी तक काफी काम नहीं करता है)। लेकिन चूंकि ग्रिड 10x10 हो सकता है यह बहुत धीमा हो जाएगा। क्या कोई बेहतर (तेज) समाधान/दृष्टिकोण सुझा सकता है?
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
int m, found;
string letters;
vector<int> done;
vector<string> a;
int ok(char letter, int c, int r)
{
int val = letter - 'A' + 1;
//checking if no side goes outside
if (r == 0 && (val & 1))
return 0;
if (r == m - 1 && (val & 4))
return 0;
if (c == 0 && (val & 8))
return 0;
if (c == m - 1 && (val & 2))
return 0;
//check if the side is connected the other pipe on the grid
if (r > 0 && a[r - 1][c] != '?' && (a[r - 1][c] & 4) && !(val & 1))
return 0;
if (c > 0 && a[r][c - 1] != '?' && (a[r][c - 1] & 2) && !(val & 8))
return 0;
if (r < m - 1 && a[r + 1][c] != '?' && (a[r + 1][c] & 1) && !(val & 4))
return 0;
if (c < m - 1 && a[r][c + 1] != '?' && (a[r][c + 1] & 8) && !(val & 2))
return 0;
return 1;
}
void solve(int num_placed, int pos)
{
if (found) return;
//done
if (num_placed == sz(letters)) {
for (int i = 0; i < m; ++i)
cout << a[i] << endl;
found = 1;
return;
}
int c = pos % m;
int r = pos/m;
if (a[r][c] != '?')
solve(num_placed, pos + 1);
//try all the pipes on this position
for (int i = 0; i < sz(letters); ++i) {
if (!done[i] && ok(letters[i], c, r)) {
a[r][c] = letters[i];
done[i] = 1;
solve(num_placed + 1, pos + 1);
done[i] = 0;
a[r][c] = '?';
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
int n;
cin >> n;
while (n--) {
cin >> m;
cin >> letters;
cout << m << endl;
a.clear();
for (int i = 0; i < m; ++i) {
string line;
cin >> line;
a.pb(line);
}
done = vector<int>(sz(letters), 0);
found = 0;
solve(0, 0);
}
return 0;
}
आपने इनपुट से लिंक किया है, समस्या का विवरण नहीं। – Bart
समस्या का विवरण जैसा दिखता है: http://www.vlaamseprogrammeerwedstrijd.be/2011/opgaves/cat2-2011/loodgieter.pdf – fgb
हाँ, आप सही हैं। मैंने यूआरएल बदल दिया। – Jasper