Submission #42894

#TimeUsernameProblemLanguageResultExecution timeMemory
42894almasalmasCultivation (JOI17_cultivation)C++14
5 / 100
2134 ms262144 KiB
#include <bits/stdc++.h> using namespace std; vector <int> qwe; vector <vector <int> > a; queue <vector <vector <int> > > q; map <vector <vector <int> >, int > used; int n, m; void show (vector <vector <int> > v) { for (int i = 1;i <= n;i ++) { for (int j = 1;j <= m;j ++) { cout << v[i][j] << ' '; } cout << endl; } } int main () { ios_base::sync_with_stdio (0); cin.tie (0), cout.tie (0); cin >> n >> m; qwe.push_back (0); int t; cin >> t; for (int i = 0;i <= n;i ++) { a.push_back (qwe); } for (int i = 0;i <= n;i ++) { for (int j = 1;j <= m;j ++) { a[i].push_back (0); } } for (int i = 1;i <= t;i ++) { int x, y; cin >> x >> y; a[x][y] = 1; } q.push (a); used[a] = 1; int almas = 0; while (!q.empty ()) { vector <vector <int> > cur = q.front (); bool ok = 0; for (int i = 1;i <= n;i ++) { for (int j = 1;j <= m;j ++) { if (cur[i][j] == 0) ok = 1; } } // cout << "NEW\n"; // show (cur); // cout << endl; q.pop (); if (!ok) { int mx = 0; for (int i = 0;i <= n;i ++) { for (int j = 0;j <= m;j ++) { mx = max (mx, cur[i][j] - 1); // cout << cur[i][j] - 1 << ' ' ; } //cout << endl; } cout << mx; return 0; } vector <vector <int> > nw = cur; int lvl = used[cur]; for (int i = 1;i < n;i ++) { for (int j = 1;j <= m;j ++) { if (cur[i][j] == 0 && cur[i + 1][j]) { nw[i][j] = lvl + 1; } } } // show (nw); // cout << endl; if (!used[nw]) { q.push (nw); used[nw] = lvl + 1; } nw = cur; for (int i = 2;i <= n;i ++) { for (int j = 1;j <= m;j ++) { if (cur[i][j] == 0 && cur[i - 1][j]) { nw[i][j] = lvl + 1; } } } // show (nw); // cout << endl; if (!used[nw]) { used[nw] = lvl + 1; q.push (nw); } nw = cur; for (int i = 1;i <= n;i ++) { for (int j = 1;j < m;j ++) { if (cur[i][j] == 0 && cur[i][j + 1]) { nw[i][j] = lvl + 1; } } } // show (nw); // cout << endl; if (!used[nw]) { used[nw] = lvl + 1; q.push (nw); } nw = cur; for (int i = 1;i <= n;i ++) { for (int j = 2;j <= m;j ++) { if (cur[i][j] == 0 && cur[i][j - 1]) { nw[i][j] = lvl + 1; } } } // show (nw); // cout << endl; // cout << "End"; //exit (0); if (!used[nw]) { used[nw] = lvl + 1; q.push (nw); } nw = cur; almas ++; // if (almas == 2) return 0; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...