Elegant Showroom

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

string s[444];

int dt[444][444];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int r,c;
	cin>>r>>c;
	for (int i=0;i<r;i++){
		cin>>s[i];
	}
	int x,y;
	cin>>x>>y;
	x--;
	y--;
	for (int i=0;i<r;i++){
		for (int ii=0;ii<c;ii++){
			dt[i][ii]=1e8;
		}
	}
	deque<pair<int, int> > bfs;
	bfs.push_back({x, y});
	dt[x][y]=1;
	while (!bfs.empty()){
		auto t=bfs.front();
		bfs.pop_front();
		for (int i=-1;i<=1;i++){
			for (int ii=-1;ii<=1;ii++){
				if ((i==0)^(ii==0)){
					int nx=t.F+i;
					int ny=t.S+ii;
					if (nx<0||ny<0||nx>=r||ny>c) continue;
					if (s[nx][ny]=='c'){
						if (dt[nx][ny]==0||dt[t.F][t.S]+1<dt[nx][ny]){
							dt[nx][ny]=dt[t.F][t.S]+1;
							bfs.push_back({nx, ny});
						}
					}
					else if(s[nx][ny]=='D'){
						if (dt[nx][ny]==0||dt[t.F][t.S]<dt[nx][ny]){
							dt[nx][ny]=dt[t.F][t.S];
							bfs.push_front({nx, ny});
						}
					}
				}
			}
		}
	}
	int v=1e9;
	for (int i=0;i<r;i++){
		if (s[i][0]=='D') v=min(v, dt[i][0]);
		if (s[i][c-1]=='D') v=min(v, dt[i][c-1]);
	}
	for (int i=0;i<c;i++){
		if (s[0][i]=='D') v=min(v, dt[0][i]);
		if (s[r-1][i]=='D') v=min(v, dt[r-1][i]);
	}
	cout<<v<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED