CSES - UKIEPC 2016

CSES - UKIEPC 2016 - Results

Submission details
Task:	Elegant Showroom
Sender:	#dt-lapset
Submission time:	2016-11-12 13:48:11 +0200
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.06 s	details
#2	ACCEPTED	0.05 s	details
#3	ACCEPTED	0.06 s	details
#4	ACCEPTED	0.09 s	details
#5	ACCEPTED	0.09 s	details
#6	ACCEPTED	0.06 s	details
#7	ACCEPTED	0.07 s	details
#8	ACCEPTED	0.07 s	details
#9	ACCEPTED	0.06 s	details
#10	ACCEPTED	0.06 s	details
#11	ACCEPTED	0.06 s	details
#12	ACCEPTED	0.06 s	details
#13	ACCEPTED	0.07 s	details
#14	ACCEPTED	0.06 s	details
#15	ACCEPTED	0.06 s	details
#16	ACCEPTED	0.06 s	details

Code

#include <bits/stdc++.h>
#define INF 999999999
#define F first
#define S second
using namespace std;

char c[444][444];
int d[444][444];
bool b[444][444];

int main () {
    int n, m;
    cin>>n>>m;
    for (int y = 1; y <= n; y++) {
        for (int x = 1 ; x <= m; x++) cin>>c[y][x];
    }
    for (int y = 0; y <= n + 1; y++) {
        for (int x = 0 ; x <= m + 1; x++) d[y][x] = INF;
    }
    int x, y;
    cin>>y>>x;
    priority_queue<pair<int, pair<int, int>>> q;
    q.push({0, {y, x}});
    d[y][x] = 0;
    while (!q.empty()) {
        int y = q.top().S.F;
        int x = q.top().S.S;
        int e = -q.top().F;
        q.pop();
        if (!y || !x || x == m + 1 || y == n + 1) continue;
        if (c[y][x] == '#') continue;
        if (b[y][x]) continue;
        b[y][x] = 1;
        if (d[y][x + 1] > e + (c[y][x + 1] == 'c')) d[y][x + 1] = e + (c[y][x + 1] == 'c'), q.push({-e + -(c[y][x + 1] == 'c'), {y, x + 1}});
        if (d[y][x - 1] > e + (c[y][x - 1] == 'c')) d[y][x - 1] = e + (c[y][x - 1] == 'c'), q.push({-e + -(c[y][x - 1] == 'c'), {y, x - 1}});
        if (d[y + 1][x] > e + (c[y + 1][x] == 'c')) d[y + 1][x] = e + (c[y + 1][x] == 'c'), q.push({-e + -(c[y + 1][x] == 'c'), {y + 1, x}});
        if (d[y - 1][x] > e + (c[y - 1][x] == 'c')) d[y - 1][x] = e + (c[y - 1][x] == 'c'), q.push({-e + -(c[y - 1][x] == 'c'), {y - 1, x}});
    }
    int ans = INF;
    for (int y = 1; y <= n; y++) {
        if (c[y][1] == 'D') ans = min(ans, d[y][1]);
        if (c[y][m] == 'D') ans = min(ans, d[y][m]);
    }
    for (int x = 1; x <= m; x++) {
        if (c[1][x] == 'D') ans = min(ans, d[1][x]);
        if (c[n][x] == 'D') ans = min(ans, d[n][x]);
    }
    
    cout<<ans + (c[y][x] == 'c')<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
`20 20 DDDDDDDDDDD##DD#DD#D DDccccc#c##c##cDccDD Dc#c#c#cc#ccc#c#Dc#D DccDc#Dc####ccc#c#DD ...` view save

correct output
`3` view save

user output
`3` view save

Test 2

Verdict: ACCEPTED

input
`20 20 #################### #cccccccccccccccccc# #c################c# #c#cccccccccccccc#c# ...` view save

correct output
`179` view save

user output
`179` view save

Test 3

Verdict: ACCEPTED

input
`20 20 #################### #cccccccccccccccccc# #cccccccccccccccccc# #cccccccccccccccccc# ...` view save

correct output
`35` view save

user output
`35` view save

Test 4

Verdict: ACCEPTED

input
`400 400 DDD##D#DD##DDDDDDDD#DDDD###DDD...` view save

correct output
`63` view save

user output
`63` view save

Test 5

Verdict: ACCEPTED

input
`400 400 #DDD###D#DD#DD#DD##DDD##D#DDD#...` view save

correct output
`11` view save

user output
`11` view save

Test 6

Verdict: ACCEPTED

input
`400 400 DDDDDDD#D#DDDD##D#DDDDDDD#DD##...` view save

correct output
`37` view save

user output
`37` view save

Test 7

Verdict: ACCEPTED

input
`400 400 #######D#DDD#D##DD####DDDDDD##...` view save

correct output
`55` view save

user output
`55` view save

Test 8

Verdict: ACCEPTED

input
`400 400 DD############################...` view save

correct output
`184` view save

user output
`184` view save

Test 9

Verdict: ACCEPTED

input
`20 20 DDDDD#DDDDDDDDD##D#D DccccD#DccccDcDD#c#D Dc###DD#c#ccDcccc#DD DccDc##DccccDcccc#DD ...` view save

correct output
`4` view save

user output
`4` view save

Test 10

Verdict: ACCEPTED

input
`5 6 ####D# #DDDD# #D##c# #DDDc# ...` view save

correct output
`1` view save

user output
`1` view save

Test 11

Verdict: ACCEPTED

input
`20 20 DDDDDD#DDDDDD#D#D#D# Dc#cccccccDcc#ccccDD DDcD#c##cDcc####Dc#D D#Dcccc#D##ccc#c#D#D ...` view save

correct output
`5` view save

user output
`5` view save

Test 12

Verdict: ACCEPTED

input
`20 20 DDD#DDDD#DDDD#DDDD#D Dc##DDccDccD#DDcDDDD DcDDccc#cc#ccc##D##D DcccD#cDc##Dcccc##D# ...` view save

correct output
`3` view save

user output
`3` view save

Test 13

Verdict: ACCEPTED

input
`20 20 #D###DD##DDDDDD###DD DDcDDccccDccDccDcc#D DcD##ccc#cDcDccccDD# DDcccc#Dc####c##ccDD ...` view save

correct output
`7` view save

user output
`7` view save

Test 14

Verdict: ACCEPTED

input
`6 7 ####### #ccc#cD #c#c#c# #c#c#c# ...` view save

correct output
`14` view save

user output
`14` view save

Test 15

Verdict: ACCEPTED

input
`5 5 DDDDD DDDDD DDcDD DDDDD ...` view save

correct output
`1` view save

user output
`1` view save

Test 16

Verdict: ACCEPTED

input
`3 3 ### #cD ### 2 2` view save

correct output
`1` view save

user output
`1` view save

UKIEPC 2016

Elegant Showroom

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (#dt-lapset)