| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 590516 |
2022-07-06T05:03:35 Z |
반딧불(#8412) |
Golf (JOI17_golf) |
C++17 |
|
1 ms |
580 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};
struct dat{
int x, y, d;
dat(){}
dat(int x, int y, int d): x(x), y(y), d(d){}
};
int n;
int H, W;
int sx, sy, ex, ey;
int ax[100002], ay[100002], bx[100002], by[100002];
bool board[4010][4010];
int able[4010][4010];
int dist[4010][4010][4];
deque<dat> que;
void renumber(){
vector<int> xVec = {-1, sx, ex};
vector<int> yVec = {-1, sy, ey};
for(int i=1; i<=n; i++){
xVec.push_back(ax[i]-1);
xVec.push_back(ax[i]);
xVec.push_back(bx[i]);
xVec.push_back(bx[i]+1);
yVec.push_back(ay[i]-1);
yVec.push_back(ay[i]);
yVec.push_back(by[i]);
yVec.push_back(by[i]+1);
}
sort(xVec.begin(), xVec.end());
xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
sort(yVec.begin(), yVec.end());
yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end());
for(int i=1; i<=n; i++){
ax[i] = lower_bound(xVec.begin(), xVec.end(), ax[i]) - xVec.begin();
bx[i] = lower_bound(xVec.begin(), xVec.end(), bx[i]) - xVec.begin();
ay[i] = lower_bound(yVec.begin(), yVec.end(), ay[i]) - yVec.begin();
by[i] = lower_bound(yVec.begin(), yVec.end(), by[i]) - yVec.begin();
}
sx = lower_bound(xVec.begin(), xVec.end(), sx) - xVec.begin();
ex = lower_bound(xVec.begin(), xVec.end(), ex) - xVec.begin();
sy = lower_bound(yVec.begin(), yVec.end(), sy) - yVec.begin();
ey = lower_bound(yVec.begin(), yVec.end(), ey) - yVec.begin();
H = (int)xVec.size()-1;
W = (int)yVec.size()-1;
}
void init(){
for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) for(int d=0; d<4; d++) dist[i][j][d] = 1e9;
for(int i=1; i<=n; i++){
for(int x=ax[i]; x<bx[i]; x++){
for(int y=ay[i]; y<by[i]; y++){
board[x][y] = 1;
}
}
}
for(int i=1; i<=H; i++){
for(int j=1; j<=W; j++){
if(j!=H && (!board[i][j] || !board[i-1][j])) able[i][j]|=1;
if(i!=W && (!board[i][j] || !board[i][j-1])) able[i][j]|=2;
if(j!=1 && (!board[i][j-1] || !board[i-1][j-1])) able[i][j]|=4;
if(i!=1 && (!board[i-1][j] || !board[i-1][j-1])) able[i][j]|=8;
}
}
for(int i=0; i<4; i++){
que.push_back(dat(sx, sy, i));
dist[sx][sy][i] = 1;
}
}
void solve(){
while(!que.empty()){
dat tmp = que.front(); que.pop_front();
int x = tmp.x, y = tmp.y, dir = tmp.d;
int len = dist[x][y][dir];
// printf("%d %d %d: %d\n", x, y, dir, len);
for(int tdir = 0; tdir < 4; tdir++){
if((able[x][y] & (1<<tdir)) == 0) continue;
if(dist[x+xx[tdir]][y+yy[tdir]][tdir] < 1e9) continue;
dist[x+xx[tdir]][y+yy[tdir]][tdir] = len + (tdir != dir);
if(tdir == dir) que.push_front(dat(x+xx[tdir], y+yy[tdir], tdir));
else que.push_back(dat(x+xx[tdir], y+yy[tdir], tdir));
}
}
}
int main(){
scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d %d %d %d", &ax[i], &bx[i], &ay[i], &by[i]);
}
renumber();
init();
solve();
printf("%d", *min_element(dist[ex][ey], dist[ex][ey]+4));
}
Compilation message
golf.cpp: In function 'int main()':
golf.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
golf.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d %d %d %d", &ax[i], &bx[i], &ay[i], &by[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
