Submission #711931

#	Time	Username	Problem	Language	Result	Execution time	Memory
711931		Karpin	Portals (BOI14_portals)	C++14	0 / 100	1 ms	468 KiB

portals

#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define vt vector
#define ar array

int r, c;


vt<string> mymap;
int depth[1002][1002];

int minRes = 1000 * 1000 * 2;

set<pair<int, int>> visited;

pair<int, int> findPortal(pair<int, int> cur, pair<int, int> direction){
    while(cur.first >= 0 && cur.first < c && cur.second >= 0 && cur.second < r && mymap[cur.first][cur.second] != '#'){
        cur.first += direction.first;
        cur.second += direction.second;
    }
    cur.first -= direction.first;
    cur.second -= direction.second;
    return cur;
}


void bfs(pair<int, int> cur){


    if (mymap[cur.first][cur.second] == 'C'){
        cout << depth[cur.first][cur.second] << endl;
        exit(0);
    }

    if (visited.find(cur) != visited.end()) return;
    visited.insert(cur);

    depth[cur.first][cur.second] = 0;

    queue<pair<int, int>> myqueue;
    myqueue.push(cur);



    while(!myqueue.empty()){
        cur = myqueue.front();
        myqueue.pop();



        if (mymap[cur.first][cur.second] == 'C'){
            cout << depth[cur.first][cur.second] << endl;
            exit(0);
        }


        pair<int, int> left;
        pair<int, int> right;
        pair<int, int> up;
        pair<int, int> down;
        if (cur.second == 0 || mymap[cur.first][cur.second - 1] == '#'){
            left = findPortal(cur, {0, 1});
        }else left = {cur.first, cur.second - 1};

        if (cur.second == c - 1 || mymap[cur.first][cur.second + 1] == '#'){
            right = findPortal(cur, {0, -1});
        }else right = {cur.first, cur.second + 1};

        if (cur.first == 0 || mymap[cur.first - 1][cur.second] == '#'){
            up = findPortal(cur, {1, 0});
        }else up = {cur.first - 1, cur.second};

        if (cur.first == r - 1 || mymap[cur.first + 1][cur.second] == '#'){
            down = findPortal(cur, {-1, 0});
        }else down = {cur.first + 1, cur.second};

        // cout << cur.first << ' ' << cur.second << endl;

        // cout << left.first << ' ' << left.second << endl;


        if (visited.find(left) == visited.end()){
            depth[left.first][left.second] = depth[cur.first][cur.second] + 1;
            visited.insert(left);
            myqueue.push(left);
        }


        if (visited.find(right) == visited.end()){
            depth[right.first][right.second] = depth[cur.first][cur.second] + 1;
            visited.insert(right);
            myqueue.push(right);
        }




        if (visited.find(up) == visited.end()){
            depth[up.first][up.second] = depth[cur.first][cur.second] + 1;
            visited.insert(up);
            myqueue.push(up);
        }


        if (visited.find(down) == visited.end()){
            depth[down.first][down.second] = depth[cur.first][cur.second] + 1;
            visited.insert(down);
            myqueue.push(down);
        }

    }

}


void solve(){
		
    cin >> r >> c;

    pair<int, int> startPoint;

    bool torf = true;

    for (int i = 0; i < r; i++){
        string my;
        cin >> my;
        if (torf)
            for (int j = 0; j < c; j++){
                if (my[j] == 'S'){
                    startPoint = {i, j};
                    torf = false;
                }
            }
        mymap.push_back(my);
    }


    bfs(startPoint);
    

}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int testcases = 1;

	// cin >> testcases;

	while(testcases--){
		solve();
	}

	return 0;

}

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