Submission #711971

#	Time	Username	Problem	Language	Result	Execution time	Memory
711971		Karpin	Portals (BOI14_portals)	C++14	20 / 100	84 ms	9300 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];

map<pair<int, int>, pair<int, int>> portalToRight;
map<pair<int, int>, pair<int, int>> portalToLeft;
map<pair<int, int>, pair<int, int>> portalToUp;
map<pair<int, int>, pair<int, int>> portalToDown;

int minRes = 1000 * 1000 * 2;

set<pair<int, int>> visited;

queue<pair<int, int>> curPortals;

bool wasPortal[1002][1002];

// pair<int, int> findPortal(pair<int, int> cur, pair<int, int> direction){
//     while(cur.first >= 0 && cur.first < r && cur.second >= 0 && cur.second < c && 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;

            // for (int i = 0; i < r; i++){
            //     for (int j = 0; j < c; j++){
            //         cout << depth[i][j] << ' ';
            //     }
            //     cout << endl;
            // }
            exit(0);
        }


        pair<int, int> left;
        pair<int, int> right;
        pair<int, int> up;
        pair<int, int> down;

        bool hasWall = false;


        if (cur.second == 0 || mymap[cur.first][cur.second - 1] == '#'){
            hasWall = true;
        }else {
            left = {cur.first, cur.second - 1};
            if (visited.find(left) == visited.end()){
                depth[left.first][left.second] = depth[cur.first][cur.second] + 1;
                visited.insert(left);
                myqueue.push(left);
                depth[left.first][left.second] = depth[cur.first][cur.second] + 1;
            }
        }

        if (cur.second == c - 1 || mymap[cur.first][cur.second + 1] == '#'){
            hasWall = true;
        }else {
            right = {cur.first, cur.second + 1};
             if (visited.find(right) == visited.end()){
                depth[right.first][right.second] = depth[cur.first][cur.second] + 1;
                visited.insert(right);
                myqueue.push(right);
                depth[right.first][right.second] = depth[cur.first][cur.second] + 1;
            }
        }

        if (cur.first == 0 || mymap[cur.first - 1][cur.second] == '#'){
            hasWall = true;
        }else {
            up = {cur.first - 1, cur.second};
            if (visited.find(up) == visited.end()){
                depth[up.first][up.second] = depth[cur.first][cur.second] + 1;
                visited.insert(up);
                myqueue.push(up);
                depth[up.first][up.second] = depth[cur.first][cur.second] + 1;
            }
        }

        if (cur.first == r - 1 || mymap[cur.first + 1][cur.second] == '#'){
            hasWall = true;
        }else {
            down = {cur.first + 1, cur.second};
            if (visited.find(down) == visited.end()){
                depth[down.first][down.second] = depth[cur.first][cur.second] + 1;
                visited.insert(down);
                myqueue.push(down);
                depth[down.first][down.second] = depth[cur.first][cur.second] + 1;
            }
        }

        if (!wasPortal[portalToRight[cur].first][portalToRight[cur].second]){
            wasPortal[portalToRight[cur].first][portalToRight[cur].second] = true;
            if (visited.find(portalToRight[cur]) == visited.end()){
                curPortals.push(portalToRight[cur]);
                visited.insert(portalToRight[cur]);
            }
        }
        if (!wasPortal[portalToLeft[cur].first][portalToLeft[cur].second]){
            wasPortal[portalToLeft[cur].first][portalToLeft[cur].second] = true;
            if (visited.find(portalToLeft[cur]) == visited.end()){
                curPortals.push(portalToLeft[cur]);
                visited.insert(portalToLeft[cur]);
            }
        }
        if (!wasPortal[portalToUp[cur].first][portalToUp[cur].second]){
            wasPortal[portalToUp[cur].first][portalToUp[cur].second] = true;
            if (visited.find(portalToUp[cur]) == visited.end()){
                curPortals.push(portalToUp[cur]);
                visited.insert(portalToUp[cur]);
            }
        }
        if (!wasPortal[portalToDown[cur].first][portalToDown[cur].second]){
            wasPortal[portalToDown[cur].first][portalToDown[cur].second] = true;
            if (visited.find(portalToDown[cur]) == visited.end()){
                curPortals.push(portalToDown[cur]);
                visited.insert(portalToDown[cur]);
            }
        }


        if (hasWall){
            while(!curPortals.empty()){
                pair<int, int> s = curPortals.front();
                curPortals.pop();
                myqueue.push(s);
                depth[s.first][s.second] = depth[cur.first][cur.second] + 1;
            }
        }





        

    }

}


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);
    }

    queue<pair<int, int>> allToBeAdded;

    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            if (mymap[i][j] != '#') allToBeAdded.push({i, j});
            else {
                while(!allToBeAdded.empty()){
                    pair<int, int> s = allToBeAdded.front();
                    allToBeAdded.pop();
                    portalToRight[s] = {i, j - 1};
                }
            }
        }
        while(!allToBeAdded.empty()){
            pair<int, int> s = allToBeAdded.front();
            allToBeAdded.pop();
            portalToRight[s] = {i, c - 1};
        }
    }

    // while(!allToBeAdded.empty()){
    //     allToBeAdded.pop();
    // }

    for (int i = 0; i < r; i++){
        for (int j = c - 1; j >= 0; j--){
            if (mymap[i][j] != '#') allToBeAdded.push({i, j});
            else {
                while(!allToBeAdded.empty()){
                    pair<int, int> s = allToBeAdded.front();
                    allToBeAdded.pop();
                    portalToLeft[s] = {i, j + 1};
                }
            }
        }
        while(!allToBeAdded.empty()){
            pair<int, int> s = allToBeAdded.front();
            allToBeAdded.pop();
            portalToLeft[s] = {i, 0};
        }
    }
    // while(!allToBeAdded.empty()){
    //     allToBeAdded.pop();
    // }

    for (int j = 0; j < c; j++){
        for (int i = 0; i < r; i++){
            if (mymap[i][j] != '#') allToBeAdded.push({i, j});
            else {
                while(!allToBeAdded.empty()){
                    pair<int, int> s = allToBeAdded.front();
                    allToBeAdded.pop();
                    portalToDown[s] = {i - 1, j};
                }
            }
        }
        while(!allToBeAdded.empty()){
            pair<int, int> s = allToBeAdded.front();
            allToBeAdded.pop();
            portalToDown[s] = {r - 1, j};
        }
    }

    // while(!allToBeAdded.empty()){
    //     allToBeAdded.pop();
    // }

    for (int j = 0; j < c; j++){
        for (int i = r - 1; i >= 0; i--){
            if (mymap[i][j] != '#') allToBeAdded.push({i, j});
            else {
                while(!allToBeAdded.empty()){
                    pair<int, int> s = allToBeAdded.front();
                    allToBeAdded.pop();
                    portalToUp[s] = {i + 1, j};
                }
            }
        }
        while(!allToBeAdded.empty()){
            pair<int, int> s = allToBeAdded.front();
            allToBeAdded.pop();
            portalToUp[s] = {0, j};
        }
    }


    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: 20 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30