제출 #442552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442552		hivakarami	포탈들 (BOI14_portals)	C++14	70 / 100	1099 ms	185888 KiB

portals

#include<bits/stdc++.h>

 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>

 
const int N = 1000 + 1;
const int inf = 1e6 + 10;
const ll mod = 924844033;
const int lg = 20;


int n, m;
int dis[N][N], d[N][N];
int U[N][N], D[N][N], L[N][N], R[N][N];
set<pair<int, pii>> s;
vector<pair<pii, int>> adj[N][N];
bool a[N][N];
char tmp[N];

inline void dij()
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			s.insert({dis[i][j], {i, j}});
		}
	}
	
	
	while(s.size())
	{
		int i = s.begin()->s.f, j = s.begin()->s.s;
		s.erase(s.begin());
		
		for(auto it : adj[i][j])
		{
			int x = it.f.f, y = it.f.s, w = it.s; 
			if(dis[x][y] > w + dis[i][j])
			{
				s.erase({dis[x][y], {x, y}});
				dis[x][y] = dis[i][j] + w;
				s.insert({dis[x][y], {x, y}});
			}
		}
	}
	
}


int main()
{
    
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	


	scanf("%d %d", &n, &m);
	//cin >> n >> m;
	pii C;
	for(int i = 0; i < n; i++)
	{
		scanf("%s", &tmp);
		for(int j = 0; j < m; j++)
		{
			
			dis[i][j] = d[i][j] = inf;
			if(tmp[j] == 'S')
				dis[i][j] = 0;
			else if(tmp[j] == 'C')
				C = {i, j};
				
			a[i][j] = (tmp[j] != '#');	
		}
	}
	
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(j == 0 || !a[i][j-1])
				U[i][j] = j;
			else
				U[i][j] = U[i][j-1];
				
				
			d[i][j] = min(d[i][j], j - U[i][j]);	
		}
		
		
		for(int j = m-1; j >= 0; j--)
		{
			if(j == m-1 || !a[i][j+1])
				D[i][j] = j;
			else
				D[i][j] = D[i][j+1];
				
			d[i][j] = min(d[i][j], D[i][j] - j);		
		}
	}
	
	
	for(int j = 0; j < m; j++)
	{
		//cout << j << '\n';	
		for(int i = 0; i < n; i++)
		{
			if(i == 0 || !a[i-1][j])
				L[i][j] = i;
			else
				L[i][j] = L[i-1][j];
			
			d[i][j] = min(d[i][j], i - L[i][j]);
				
		}
		
		for(int i = n-1; i >= 0; i--)
		{	
			if(i == n-1 || !a[i+1][j])
				R[i][j] = i;
			else
				R[i][j] = R[i+1][j];
			
			d[i][j] = min(d[i][j], R[i][j] - i);
		}
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(!a[i][j])
				continue;
			adj[i][j].pb({{i, U[i][j]}, d[i][j] + 1});
			adj[i][j].pb({{i, D[i][j]}, d[i][j] + 1});
			adj[i][j].pb({{L[i][j], j}, d[i][j] + 1});
			adj[i][j].pb({{R[i][j], j}, d[i][j] + 1});
			
			if(i > 0 && a[i-1][j])
				adj[i][j].pb({{i-1, j}, 1});
			
			if(j > 0 && a[i][j-1])
				adj[i][j].pb({{i, j-1}, 1});
				
			if(i < n-1 && a[i+1][j])
				adj[i][j].pb({{i+1, j}, 1});
			
			if(j < m-1 && a[i][j+1])
				adj[i][j].pb({{i, j+1}, 1});
				
				
			//cout << i << ' ' << j << endl;	
				
		}
	}
	
	
	dij();
	
	printf("%d", dis[C.f][C.s]);
	//cout << dis[C.f][C.s];
		


	return 0;
}



 

컴파일 시 표준 에러 (stderr) 메시지

portals.cpp: In function 'int main()':
portals.cpp:70:11: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1001]' [-Wformat=]
   70 |   scanf("%s", &tmp);
      |          ~^   ~~~~
      |           |   |
      |           |   char (*)[1001]
      |           char*
portals.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
portals.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%s", &tmp);
      |   ~~~~~^~~~~~~~~~~~

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