| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 711971 |
2023-03-17T19:47:05 Z |
Karpin |
Portals (BOI14_portals) |
C++14 |
|
84 ms |
9300 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
71 ms |
8148 KB |
Output is correct |
| 6 |
Correct |
84 ms |
8496 KB |
Output is correct |
| 7 |
Correct |
61 ms |
8572 KB |
Output is correct |
| 8 |
Correct |
75 ms |
9300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
