Submission #489285

#	Time	Username	Problem	Language	Result	Execution time	Memory
489285		MilosMilutinovic	Portals (BOI14_portals)	C++17	20 / 100	21 ms	27484 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=1010;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,m,vis[N][N],dis[N][N];
char s[N][N];
vector<PII> e[N][N];

int main() {
	scanf("%d%d",&n,&m);
	rep(i,0,n) scanf("%s",s[i]);
	int sx,sy;
	rep(i,0,n) rep(j,0,m) {
		if (s[i][j]=='#') continue;
		if (s[i][j]=='S') sx=i,sy=j;
		rep(d,0,4) {
			int ni=i+dx[d],nj=j+dy[d];
			if (ni>=0&&ni<n&&nj>=0&&nj<m&&s[ni][nj]!='#') {
				e[i][j].pb(mp(ni,nj));
			}
		}
		int xl=i;
		while (xl>0&&s[xl-1][j]!='#') xl--;
		if (xl<i-1) e[i][j].pb(mp(xl,j));
		int xr=i;
		while (xr+1<n&&s[xr+1][j]!='#') xr++;
		if (xr>i+1) e[i][j].pb(mp(xr,j));
		int yl=j;
		while (yl>0&&s[i][yl-1]!='#') yl--;
		if (yl<j-1) e[i][j].pb(mp(i,yl));
		int yr=j;
		while (yr+1<m&&s[i][yr+1]!='#') yr++;
		if (yr>j+1) e[i][j].pb(mp(i,yr));
	}
	deque<PII> q;
	vis[sx][sy]=1;
	dis[sx][sy]=0;
	q.pb(mp(sx,sy));
	while (SZ(q)) {
		auto [x,y]=q[0];
		q.pop_front();
		for (auto p:e[x][y]) {
			if (!vis[p.fi][p.se]) {
				vis[p.fi][p.se]=1;
				dis[p.fi][p.se]=dis[x][y]+1;
				q.pb(mp(p.fi,p.se));
			}
		}
	}
	rep(i,0,n) rep(j,0,m) if (s[i][j]=='C') printf("%d",dis[i][j]);
}

/*5 5
S###C
.###.
.###.
.###.
.....
*/

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
portals.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  rep(i,0,n) scanf("%s",s[i]);
      |             ~~~~~^~~~~~~~~~~
portals.cpp:58:15: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  q.pb(mp(sx,sy));
      |               ^
portals.cpp:58:15: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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