Submission #115981

#	Time	Username	Problem	Language	Result	Execution time	Memory
115981		Mahdi_Jfri	Portals (BOI14_portals)	C++14	100 / 100	984 ms	125552 KiB

portals

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define left leftt
#define right wrong

const int maxn = 1e3 + 20;
const int maxm = maxn * maxn + 20;
const int dx[] = {0 , 0 , 1 ,-1};
const int dy[] = {1 ,-1 , 0 , 0}; 

int d[maxm] , n , m , up[maxn][maxn] , left[maxn][maxn] , down[maxn][maxn] , right[maxn][maxn];

vector<pair<int , int> > adj[maxm];

string s[maxn];

int cd(int x , int y)
{
	return x * m + y;
}

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

	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> s[i];

	queue<int> q;
	memset(d , 63 , sizeof d);
	for(int x = 0; x < n; x++)
		for(int y = 0; y < m; y++)
		{
			if(s[x][y] == '#')
				continue;

			for(int i = 0; i < 4; i++)
			{
				int nx = x + dx[i] , ny = y + dy[i];
				if(0 <= nx && nx < n && 0 <= ny && ny < m && s[nx][ny] != '#')
					adj[cd(x , y)].pb({cd(nx , ny) , 1});
			}

			if(adj[cd(x , y)].size() != 4)
				q.push(cd(x , y)) , d[cd(x , y)] = 1;
		}

	while(!q.empty())
	{
		int v = q.front();
		q.pop();

		for(auto e : adj[v])
		{
			int u = e.first;
			if(d[u] > d[v] + 1)
				d[u] = d[v] + 1 , q.push(u);
		}
	}

	for(int x = 0; x < n; x++)
	{
		for(int y = 0; y < m; y++)
		{
			if(!y || s[x][y - 1] == '#')
				left[x][y] = cd(x , y);
			else 
				left[x][y] = left[x][y - 1];
		}

		for(int y = m - 1; y >= 0; y--)
		{
			if(y + 1 >= m || s[x][y + 1] == '#')
				right[x][y] = cd(x , y);
			else
				right[x][y] = right[x][y + 1];
		}
	}

	for(int y = 0; y < m; y++)
	{
		for(int x = 0; x < n; x++)
		{
			if(!x || s[x - 1][y] == '#')
				up[x][y] = cd(x , y);
			else
				up[x][y] = up[x - 1][y];
		}

		for(int x = n - 1; x >= 0; x--)
		{
			if(x + 1 >= n || s[x + 1][y] == '#')
				down[x][y] = cd(x , y);
			else
				down[x][y] = down[x + 1][y];
		}
	}

	int S , T;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(s[i][j] != '#')
			{
	//			cout << i + 1 << " " << j + 1 << " " << d[cd(i , j)] << endl;
	//			cout << left[i][j] << " " << right[i][j] << " " << up[i][j] << " " << down[i][j] << endl;
				adj[cd(i , j)].pb({right[i][j] , d[cd(i , j)]});
				adj[cd(i , j)].pb({left[i][j] , d[cd(i , j)]});
				adj[cd(i , j)].pb({up[i][j] , d[cd(i , j)]});
				adj[cd(i , j)].pb({down[i][j] , d[cd(i , j)]});

				if(s[i][j] == 'S')
					S = cd(i , j);
				if(s[i][j] == 'C')
					T = cd(i , j);
			}

	memset(d , 63 , sizeof d);
	d[S] = 0;
	set<pair<int , int> > st;
	st.insert({d[S] , S});

	while(!st.empty())
	{
		int v = st.begin() -> second;
		int W = st.begin() -> first;
		st.erase(st.begin());

		if(d[v] != W)
			continue;

		for(auto e : adj[v])
		{
			int w = e.second , u = e.first;
			if(d[u] > d[v] + w)
			{
				d[u] = d[v] + w;
				st.insert({d[u] , u});
			}
		}
	}

	cout << d[T] << endl;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:148:13: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << d[T] << endl;
             ^

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