| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 657845 |
2022-11-11T14:21:47 Z |
4EVER |
Patkice (COCI20_patkice) |
C++11 |
|
10 ms |
16596 KB |
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
X eps = 1e-9;
if (x > y + eps) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return true;
} else return false;
}
template<class T>
T Abs(const T &x) {
return (x < 0 ? -x : x);
}
const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int maxn = (int) 2011;
const int LOG = (int) 20;
const char dir[] = { '>', '<', 'v', '^' };
const ii dxy[] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
int n, m;
char a[maxn][maxn], b[maxn][maxn];
int dp[maxn][maxn];
ii sta, fin;
ii pre[maxn][maxn];
struct data_{
int u, v, w;
bool operator < (const data_ &others) const{
return (w > others.w);
}
};
bool OK(int u, int v){
return (u >= 1 && u <= n && v >= 1 && v <= m && (a[u][v] != 'o'));
}
void Trace(int i, int j){
bool ok = 0;
while(pre[i][j].first != -1){
int p, q;
for(int t = 0; t < 4; t++){
p = i + dxy[t].first;
q = j + dxy[t].second;
if(p == sta.first && q == sta.second){
ok = 1;
break;
}
if(p == pre[i][j].first && q == pre[i][j].second){
if(t == 0) t = 1;
else if(t == 1) t = 0;
else if(t == 2) t = 3;
else if(t == 3) t = 2;
b[p][q] = dir[t];
break;
}
}
if(ok) break;
i = p, j = q;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == 'o') cout << a[i][j];
else cout << b[i][j];
}
cout << "\n";
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TASK "PATKICE"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
if(a[i][j] == 'o') sta = {i, j};
if(a[i][j] == 'x') fin = {i, j};
pre[i][j] = {-1, -1};
b[i][j] = a[i][j];
}
}
memset(dp, 0x3f, sizeof dp);
priority_queue<data_> que;
dp[sta.first][sta.second] = 0;
que.push({sta.first, sta.second, dp[sta.first][sta.second]});
while(!que.empty()){
int u = que.top().u;
int v = que.top().v;
int du = que.top().w;
que.pop();
if(dp[u][v] != du) continue;
if(u == fin.first && v == fin.second){
cout << dp[u][v] << "\n";
Trace(u, v);
return 0;
}
if(a[u][v] == 'o'){
for(int i = 0; i < 4; i++){
int p = u + dxy[i].first;
int q = v + dxy[i].second;
if(!OK(p, q)) continue;
if(minimize(dp[p][q], dp[u][v])){
que.push({p, q, dp[p][q]});
pre[p][q] = {u, v};
}
}
}
else{
for(int i = 0; i < 4; i++){
int p, q;
p = u + dxy[i].first;
q = v + dxy[i].second;
if(!OK(p, q)) continue;
if(a[u][v] != dir[i]){
if(minimize(dp[p][q], dp[u][v] + 1)){
que.push({p, q, dp[p][q]});
pre[p][q] = {u, v};
}
}
else{
if(minimize(dp[p][q], dp[u][v])){
que.push({p,q , dp[p][q]});
pre[p][q] = {u, v};
}
}
}
}
}
return 0;
}
Compilation message
patkice.cpp: In function 'int main()':
patkice.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
patkice.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
16596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
