Submission #945625

#	Time	Username	Problem	Language	Result	Execution time	Memory
945625		vjudge1	Portals (BOI14_portals)	C++17	0 / 100	1 ms	440 KiB

portals

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> pipii;

#define mp make_pair
#define fi first
#define se second

const int INF=1e9;

int main(){
		int r, c;
		cin >> r >> c;
		char m[r][c];
		vector<int> xw[r], yw[c];
		pii sl, cl;
		for(auto && i: xw){
				i.push_back(-1);
		}
		for(auto && i: yw){
				i.push_back(-1);
		}
		for(int i=0; i<r; i++){
				for(int j=0; j<c; j++){
						cin >> m[i][j];
						if(m[i][j] == '#'){
								xw[i].push_back(j);
								yw[j].push_back(i);
						}
						else if(m[i][j] == 'S'){
								sl = mp(i, j);
						}
						else if(m[i][j] == 'C'){
								cl = mp(i, j);
						}
				}
		}
		for(auto && i: xw){
				i.push_back(c);
		}
		for(auto && i: yw){
				i.push_back(r);
		}
		queue<pii> wq;
		int dw[r][c];
		memset(dw, -1, sizeof(dw));
		vector<pipii> al[r][c];
		const int dx[] = {-1, 1, 0, 0};
		const int dy[] = {0, 0, -1, 1};
		for(int i=0; i<r; i++){
				for(int j=0; j<c; j++){
						for(int k=0; k<4; k++){
								int nx = i+dx[k], ny = j+dy[k];
								if(nx == -1 || ny == -1 || nx == r || ny== c || m[nx][ny] == '#'){
										if(dw[i][j] == 1) continue;
										wq.emplace(i, j);
										dw[i][j] = 1;
								}
								else{
										al[i][j].emplace_back(1, mp(nx, ny));
								}
						}
				}
		}
		while(wq.size()){
				auto[cx, cy] = wq.front();
				wq.pop();
				for(int k=0; k<4; k++){
						int nx = cx+dx[k], ny = cy+dy[k];
						if(nx == -1 || ny == -1 || nx == r || ny == c) continue;
						if(m[nx][ny] == '#') continue;
						if(dw[nx][ny] != -1) continue;
						dw[nx][ny] = dw[cx][cy] + 1;
						wq.emplace(cx, cy);
				}
		}	
		for(int i=0; i<r; i++){
				for(int j=0; j<c; j++){
						if(m[i][j] == '#') continue;
						vector<int>::iterator xw1, xw2, yw1, yw2;
						xw2 = upper_bound(xw[i].begin(), xw[i].end(), j);
						xw1 = xw2-1;
						yw2 = upper_bound(yw[j].begin(), yw[j].end(), i);
						yw1 = yw2-1;
				}
		}
		priority_queue<pipii, vector<pipii>, greater<pipii>> pq;
		int dst[r][c];
		bool visited[r][c];
		for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			dst[i][j] = INF;
		}
	}
		memset(visited, 0, sizeof(visited));
		dst[sl.fi][sl.se] = 0;
		pq.emplace(0, sl);
		while(pq.size()){
				auto[cd, cxy] = pq.top();
				pq.pop();
				auto[cx, cy] = cxy;
				if(visited[cx][cy]) continue;
				for(auto [nw, nxy] : al[cx][cy]){
						auto[nx, ny] = nxy;
						if(dst[nx][ny] > cd+nw){
								dst[nx][ny] = cd+nw;
								pq.emplace(dst[nx][ny], nxy);
						}
				}
				visited[cx][cy] = true;
		}
		cout << dst[cl.fi][cl.se];
		return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30