My DFS solution to the problem D - Grid Coloring is failing one Test Case.
My Code:
// Author: Muhesh Kumar
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vs = vector<string>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
#define nl '\n'
#define fr first
#define sc second
#define bk back()
#define ft front()
#define pb push_back
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sz(x) (int) (x).size()
#define amax(a, b) a = max(a, b)
#define amin(a, b) a = min(a, b)
#define trav(a, b) for(auto &a: b)
#define rep(i, a, b) for(int i = a; i < b; i++)
const ll inf = 1e18 + 10;
const db eps = 1e-9;
const int mod = 1e9 + 7;
ll modadd(ll a, ll b, ll m = mod) { a %= m; b %= m; return (((a + b) % m) + m) % m; }
ll modsub(ll a, ll b, ll m = mod) { a %= m; b %= m; return (((a - b) % m) + m) % m; }
ll modmul(ll a, ll b, ll m = mod) { a %= m; b %= m; return (((a * b) % m) + m) % m; }
ll gcd(ll a, ll b) { return __gcd(a, b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template <typename T1, typename T2>
inline std::ostream &operator << (std::ostream& os, const std::pair<T1, T2>& p) {
return os << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
inline std::ostream &operator << (std::ostream& os,const std::vector<T>& v) {
bool first = true;
os << "[";
for(unsigned int i = 0; i < v.size(); i++) {
if(!first)
os << ", ";
os << v[i];
first = false;
}
return os << "]";
}
template<typename T>
inline std::ostream &operator << (std::ostream& os,const std::vector<vector<T>>& v) {
bool first = true;
os << "[\n ";
for(unsigned int i = 0; i < v.size(); i++) {
if(!first)
os << ",\n ";
os << v[i];
first = false;
}
return os << "\n]";
}
template<typename T>
inline std::ostream &operator << (std::ostream& os,const std::set<T>& v) {
bool first = true;
os << "[";
for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
if(!first)
os << ", ";
os << *ii;
first = false;
}
return os << "]";
}
template<typename T1, typename T2>
inline std::ostream &operator << (std::ostream& os,const std::map<T1, T2>& v) {
bool first = true;
os << "[\n ";
for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {
if(!first)
os << ",\n ";
os << *ii ;
first = false;
}
return os << "\n]";
}
#ifndef ONLINE_JUDGE
#define debug(a) cerr << #a << " " << a << '\n';
#else
#define debug(a)
#endif
const int N = 110;
vvi grid(N, vi(N));
vvb visited(N, vb(N));
vi dx = {-1, 0, 1, 0};
vi dy = {0, 1, 0, -1};
bool is_valid(int x, int y, int h, int w) {
if (x < 0 || y < 0 || x >= h || y >= w)
return false;
if (visited[x][y])
return false;
return true;
}
int curr_cnt = 0;
void dfs(int x, int y, int h, int w, int color, int req_cnt) {
visited[x][y] = 1;
grid[x][y] = color;
curr_cnt++;
if (curr_cnt == req_cnt) {
return;
}
rep(i, 0, 4) {
int nx = x + dx[i];
int ny = y + dy[i];
if (is_valid(nx, ny, h, w) && curr_cnt < req_cnt) {
dfs(nx, ny, h, w, color, req_cnt);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int h, w; cin >> h >> w;
int n; cin >> n;
vi colors(n + 1);
rep(i, 1, n + 1) cin >> colors[i];
int k = 1;
rep(i, 0, h) {
rep(j, 0, w) {
if (visited[i][j]) continue;
int x = i, y = j, color = k, req_cnt = colors[k];
k++;
curr_cnt = 0;
dfs(x, y, h, w, color, req_cnt);
}
}
rep(i, 0, h) {
rep(j, 0, w) {
cout << grid[i][j] << " ";
}
cout << nl;
}
return 0;
}
The Test Case for which the code is failing:
87 97
31
381 153 583 163 273 72 202 46 84 96 42 385 13 220 134 686 293 706 635 512 547 26 197 372 97 1047 317 18 84 39 16
I tried debugging the code but couldn’t progress further and I’m not sure why my code is getting WA for this test case alone. After reading the editorial it seems there is an easier way to solve this problem, still, any help would be appreciated.
Thanks.