oj.uz

답안 #948510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948510 2024-03-18T07:25:00 Z Darren0724 포탈들 (BOI14_portals) C++17
20 / 100
 13 ms 8796 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
//#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=505;
const int INF=1e9;

int32_t main() {
    LCBorz;
    int n,m;cin>>n>>m;
    vector<vector<char>> v(n+2,vector<char>(m+2,'#'));
    auto id=[&](int a,int b){
        return a*N+b;
    };
    auto valid=[&](int a,int b){
        return v[a][b]!='#';
    };
    auto rev=[&](int id){
        return make_pair(id/N,id%N);
    };
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>v[i][j];
        }
    }
    vector<int> adj[N*N];
    for(int i=1;i<=n;i++){
        int last=0;
        for(int j=1;j<=m;j++){
            if(!valid(i,j)){
                last=j;
                continue;
            }
            adj[id(i,j)].push_back(id(i,last+1));
        }
        last=m+1;
        for(int j=m;j>=1;j--){
            if(!valid(i,j)){
                last=j;
                continue;
            }
            adj[id(i,j)].push_back(id(i,last-1));
        }
    }
    for(int i=1;i<=m;i++){
        int last=0;
        for(int j=1;j<=n;j++){
            if(!valid(j,i)){
                last=j;
                continue;
            }
            adj[id(j,i)].push_back(id(last+1,i));
        }
        last=n+1;
        for(int j=n;j>=1;j--){
            if(!valid(j,i)){
                last=j;
                continue;
            }
            adj[id(j,i)].push_back(id(last-1,i));
        }
    }
    vector<int> dx={0,0,-1,1},dy={1,-1,0,0};
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!valid(i,j))continue;
            for(int k=0;k<4;k++){
                int a=i+dx[k],b=j+dy[k];
                if(!valid(a,b))continue;
                adj[id(i,j)].push_back(id(a,b));
            }
        }
    }
    queue<int> q;
    vector<int> dis(N*N,INF);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(v[i][j]=='S'){
                q.push(id(i,j));
                dis[id(i,j)]=0;
            }
        }
    }
    while(q.size()){
        int p=q.front();
        q.pop();
        for(int j:adj[p]){
            if(dis[j]==INF){
                dis[j]=dis[p]+1;
                q.push(j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(v[i][j]=='C'){
                cout<<dis[id(i,j)]<<endl;
            }
        }
    }
    

    
    return 0;
}

Compilation message

portals.cpp: In function 'int32_t main()':
portals.cpp:20:10: warning: variable 'rev' set but not used [-Wunused-but-set-variable]
   20 |     auto rev=[&](int id){
      |          ^~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7456 KB Output is correct
2 Correct 4 ms 7256 KB Output is correct
3 Correct 4 ms 7260 KB Output is correct
4 Correct 4 ms 7260 KB Output is correct
5 Correct 10 ms 8492 KB Output is correct
6 Correct 11 ms 8536 KB Output is correct
7 Correct 11 ms 8792 KB Output is correct
8 Correct 13 ms 8796 KB Output is correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

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