#include <bits/stdc++.h>
using namespace std;
const int maxn = 305 + 10;
int a[maxn][maxn], b[maxn][maxn];
int d[maxn][maxn];
pair <int, int> par[maxn][maxn];
int n;
bool inside(int x, int y) {
return (0 <= x && x < n) && (0 <= y && y < n);
}
bool check(int x, int y) {
if(not inside(x, y)) return false;
if(inside(x + 1, y) && b[x + 1][y] == 0) return false;
if(inside(x, y + 1) && b[x][y + 1] == 0) return false;
return true;
}
pair <int, int> getOpt(vector <pair <int, int>> can) {
queue <pair <int, int>> Q;
for(auto i : can) {
Q.push(i);
d[i.first][i.second] = 0;
par[i.first][i.second] = i;
}
vector <pair <int, int>> filled;
pair <int, int> ret (-1, -1);
pair <int, int> from (-1, -1);
bool found = false;
while(not Q.empty()) {
int x = Q.front().first;
int y = Q.front().second;
int dist = d[x][y];
d[x][y] = -1;
Q.pop();
if(not found) {
if(a[x][y] == 1) {
found = true;
ret = make_pair(x, y);
from = par[x][y];
}
}
if(found) continue;
if(inside(x - 1, y) && d[x - 1][y] == -1) {
d[x - 1][y] = 1 + dist;
par[x - 1][y] = par[x][y];
Q.emplace(x - 1, y);
}
if(inside(x, y - 1) && d[x][y - 1] == -1) {
d[x][y - 1] = 1 + dist;
par[x][y - 1] = par[x][y];
Q.emplace(x, y - 1);
}
}
return ret;
}
int main() {
int t, k1, k2;
cin >> t >> n >> k1 >> k2;
queue <int> Q;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
memset(d, -1, sizeof d);
vector <pair <int, int>> can;
can.emplace_back(n - 1, n - 1);
while(true) {
auto x = getOpt(can);
if(x == make_pair(-1, -1)) break;
auto y = par[x.first][x.second];
can.erase(find(can.begin(), can.end(), y));
a[x.first][x.second] = 0;
b[y.first][y.second] = 1;
// cout << x.first << " " << x.second << endl;
// cout << y.first << " " << y.second << endl;
if(check(y.first - 1, y.second)) {
can.emplace_back(y.first - 1, y.second);
}
if(check(y.first, y.second - 1)) {
can.emplace_back(y.first, y.second - 1);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << b[i][j] << " \n"[j == n - 1];
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
K = 17 |
| 2 |
Incorrect |
7 ms |
1024 KB |
K = 594 |
| 3 |
Execution timed out |
2088 ms |
2424 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2071 ms |
2304 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2086 ms |
2304 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2087 ms |
2296 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2084 ms |
2296 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2087 ms |
2424 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2078 ms |
2620 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2089 ms |
2424 KB |
Time limit exceeded |
