#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll r,c;
ll a(ll i, ll j) {
return (i)*(c+2)+j;
}
pair<ll,ll> ra(ll x) {
return {(x)/(c+2),(x)%(c+2)};
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> r >> c;
//if (r*c>100) return 0;
ll grid[r+5][c+5];
ll s,e;
memset(grid,0,sizeof(grid));
for (int i=1;i<=r;i++){
string temp;
cin >> temp;
for (int j=1;j<=c;j++){
if (temp[j-1]=='.') grid[i][j] = 1;
else if (temp[j-1]=='#') grid[i][j] = 0;
else if (temp[j-1]=='C') {
grid[i][j] = 1;
e = a(i,j);
}
else{
grid[i][j] = 1;
s = a(i,j);
}
}
}
ll visited[r*c*2];
queue<pair<ll,ll>> bfs;
memset(visited,0,sizeof(visited));
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
if (grid[i][j]==0) continue;
ll check=0;
if (grid[i-1][j]==0) check=1;
else if (grid[i+1][j]==0) check=1;
else if (grid[i][j-1]==0) check=1;
else if (grid[i][j+1]==0) check=1;
if (check==0) continue;
bfs.push({a(i,j),0});
visited[a(i,j)]=1;
}
}
ll dist[r*c*2];
memset(dist,-1,sizeof(dist));
while (!bfs.empty()){
ll x = bfs.front().first;
ll rnk = bfs.front().second;
dist[x] = rnk;
bfs.pop();
ll item;
pair<ll,ll> temp;
item=x-1;
if (visited[item]==0){
temp = ra(item);
if (grid[temp.first][temp.second]==1){
visited[item] = 1;
bfs.push({item,rnk+1});
}
}
item=x+1;
if (visited[item]==0){
temp = ra(item);
if (grid[temp.first][temp.second]==1){
visited[item] = 1;
bfs.push({item,rnk+1});
}
}
item=x-c-2;
if (visited[item]==0){
temp = ra(item);
if (grid[temp.first][temp.second]==1){
visited[item] = 1;
bfs.push({item,rnk+1});
}
}
item=x+c+2;
if (visited[item]==0){
temp = ra(item);
if (grid[temp.first][temp.second]==1){
visited[item] = 1;
bfs.push({item,rnk+1});
}
}
}
/*
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cout << dist[a(i,j)] << " ";
}
cout << "\n";
}
*/
ll left[r*c*2],right[r*c*2],up[r*c*2],down[r*c*2];
for (int j=1;j<=c;j++) up[a(0,j)] = a(0,j);
for (int i=1;i<=r;i++){
if (grid[i][1]==0) {
left[a(i,1)]=a(i,1);
up[a(i,1)]=a(i,1);
}
else {
left[a(i,1)]=a(i,0);
up[a(i,1)] = up[a(i-1,1)];
}
for (int j=2;j<=c;j++){
if (grid[i][j]==0) {
left[a(i,j)] = a(i,j);
up[a(i,j)] = a(i,j);
}
else {
left[a(i,j)] = left[a(i,j-1)];
up[a(i,j)] = up[a(i-1,j)];
}
}
}
//right down
for (int j=1;j<=c;j++) down[a(r+1,j)] = a(r+1,j);
for (int i=r;i>=1;i--){
if (grid[i][c]==0) {
right[a(i,c)]=a(i,c);
down[a(i,c)]=a(i,c);
}
else {
right[a(i,c)]=a(i,c+1);
down[a(i,c)] = down[a(i+1,c)];
}
for (int j=c-1;j>=1;j--){
if (grid[i][j]==0) {
right[a(i,j)] = a(i,j);
down[a(i,j)] = a(i,j);
}
else {
right[a(i,j)] = right[a(i,j+1)];
down[a(i,j)] = down[a(i+1,j)];
}
}
}
/*
cout << "left\n";
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cout << ra(left[a(i,j)]).first << "," << ra(left[a(i,j)]).second << " ";
}
cout << "\n";
}
cout << "right\n";
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cout << ra(right[a(i,j)]).first << "," << ra(right[a(i,j)]).second << " ";
}
cout << "\n";
}
cout << "down\n";
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cout << ra(down[a(i,j)]).first << "," << ra(down[a(i,j)]).second << " ";
}
cout << "\n";
}
cout << "up\n";
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cout << ra(up[a(i,j)]).first << "," << ra(up[a(i,j)]).second << " ";
}
cout << "\n";
}
*/
vector<pair<ll,ll>> adj[r*c*5];
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
if (grid[i][j]==0) continue;
ll x = a(i,j);
ll item;
pair<ll,ll> temp;
item=x-1;
temp = ra(item);
if (grid[temp.first][temp.second]==1){
adj[x].push_back({item,1});
}
item=x+1;
temp = ra(item);
if (grid[temp.first][temp.second]==1){
adj[x].push_back({item,1});
}
item=x-c-2;
temp = ra(item);
if (grid[temp.first][temp.second]==1){
adj[x].push_back({item,1});
}
item=x+c+2;
temp = ra(item);
if (grid[temp.first][temp.second]==1){
adj[x].push_back({item,1});
}
adj[x].push_back({left[x]+1,dist[x]+1});
adj[x].push_back({down[x]-c-2,dist[x]+1});
adj[x].push_back({up[x]+c+2,dist[x]+1});
adj[x].push_back({right[x]-1,dist[x]+1});
}
}
/*
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cout << i << "," << j << ": ";
for (auto item:adj[a(i,j)]){
cout << ra(item.first).first << "," << ra(item.first).second << "," << item.second << " ";
}
cout << "\n";
}
}
*/
ll dis[r*c*2];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
memset(dis,-1,sizeof(dis));
dis[s]=0;
pq.push({0,s});
while (!pq.empty()) {
pair<ll,ll> cur = pq.top();
pq.pop();
ll x = cur.second, d = cur.first;
if (d>dis[x]) continue;
for (vector<pair<ll,ll>>::iterator it=adj[x].begin();it!=adj[x].end();++it){
ll nx = it->first, nd = d+it->second;
if (dis[nx]!=-1 && dis[nx]<=nd) continue;
dis[nx] = nd;
pq.push({nd,nx});
}
}
/*
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cout << dis[a(i,j)] << " ";
}
cout << "\n";
}
*/
cout << dis[e];
//cout << "a";
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:251:15: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
251 | cout << dis[e];
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
