oj.uz

답안 #735591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735591 2023-05-04T11:27:46 Z josanneo22 포탈들 (BOI14_portals) C++17
0 / 100
 1 ms 596 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define mp make_pair
#define fi first
#define se second

const int maxn=1005;
int a[maxn][maxn],ans[maxn][maxn],up[maxn][maxn],down[maxn][maxn],rt[maxn][maxn],lf[maxn][maxn];
int n,m,sx,sy,ex,ey;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct e{
	int x,y,dist;
};
class comp {
public:
    bool operator()(e f,e s)
    {
		return f.dist<s.dist;
    }
};
bool valid(int x,int y){
	if(x>=0 && x<=n-1 && y>=0 && y<=m-1 && a[x][y]==1) return true;
	else return false;
}
void init(){
	for (int i=0; i<n; i++)  
        for (int j=0; j<m; j++) 
			ans[i][j]=1e9;
	for (int i=0; i<n; i++) {
        int pre = 0;
        for (int j=0; j<m; j++) {
            if(a[i][j]==0) pre = j+1;
            rt[i][j] = pre;
        }
    }
    for (int i=0; i<n; i++) {
        int pre = m-1;
        for (int j=m-1; j>=0; j--) {
            if(a[i][j] ==0) pre = j-1;
            lf[i][j] = pre;
        }
    }
    for (int j=0; j<m; j++) {
        int pre = 0;
        for (int i=0; i<n; i++) {
            if(a[i][j] == 0) pre = i+1;
            down[i][j] = pre;
        }
    }
    for (int j=0; j<m; j++) {
        int pre = n-1;
        for (int i=n-1; i>=0; i--) {
            if(a[i][j] == 0) pre = i-1;
            up[i][j] = pre;
        }
    }
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char x; cin>>x;
			if(x=='#') a[i][j]=0;
			else a[i][j]=1;

			if(x=='S') sx=i,sy=j;
			if(x=='C') ex=i,ey=j;
		}
	}
	init();
	priority_queue<e,vector<e>,comp> pq;
	pq.push({sx,sy,0});
	while(pq.size()){
		e u=pq.top(); pq.pop();
		if(ans[u.x][u.y]<=u.dist) continue;
		ans[u.x][u.y]=u.dist;
		for(int i=0;i<4;i++){
			if(valid(u.x+dx[i],u.y+dy[i])) pq.push({u.x+dx[i],u.y+dy[i],u.dist+1});
		}
		//找到最靠近的传送门
		int mn=min({abs(u.y-up[u.x][u.y]),
					abs(u.y-down[u.x][u.y]),
					abs(u.x-rt[u.x][u.y]),
					abs(u.x-lf[u.x][u.y])
					});
		//往上下左右发射，走mn个步就可以到那里然后tp就要+1
		pq.push({u.x,lf[u.x][u.y],u.dist+mn+1});
		pq.push({u.x,lf[u.x][u.y],u.dist+mn+1});
		pq.push({up[u.x][u.y],u.y,u.dist+mn+1});
		pq.push({down[u.x][u.y],u.y,u.dist+mn+1});
	} 
	cout<<ans[ex][ey]<<'\n';
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Incorrect 1 ms 452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -