Submission details
Task:Mission
Sender: >--) ) ) )*>
Submission time:2015-10-07 18:25:18 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.06 sdetails
#20.05 sdetails
#3ACCEPTED0.06 sdetails
#40.05 sdetails
#50.05 sdetails
#60.05 sdetails
#70.05 sdetails
#80.06 sdetails
#90.06 sdetails
#100.14 sdetails
#11ACCEPTED0.06 sdetails
#120.06 sdetails
#130.05 sdetails
#140.05 sdetails
#150.05 sdetails
#160.06 sdetails
#170.14 sdetails
#180.06 sdetails
#19ACCEPTED0.05 sdetails
#200.06 sdetails
#21ACCEPTED0.05 sdetails
#220.05 sdetails
#230.05 sdetails
#240.06 sdetails
#250.05 sdetails

Compiler report

input/code.cpp: In function 'int dist(int, int, int, int)':
input/code.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < z.size(); i++) {
                    ^
input/code.cpp: In function 'int main()':
input/code.cpp:105:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                    ^
input/code.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++) {
                     ^

Code

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

#define ll long long
#define ld long double
#define ii pair<int,int>
#define si pair<string,int>
#define iii pair<int,ii>
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define msvs map<string,vs>
#define msi map<string,int>
#define mss map<string,int>
#define us unordered_set
#define um unordered_map
#define pq priority_queue
#define pb push_back
#define mp make_pair
#define forall(i,a,b) for (int i=a;i<b;i++)
#define foreach(v,c) for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a) a.begin(), a.end()
#define in(a,b) ( (b).find(a) != (b).end())
#define fill(a,v) memset(a, v, sizeof a)
#define sz(a) ((int)(a.size()))
#define N (1<<17)
#define M 1000000007
#define I 500000004

int n,m,k;
char l[100][100];
char r[100][100];
pair<int,int> a;
pair<int,int> b;
vector<pair<int,int>> v;

int dist(int y1, int x1, int y2, int x2) {
	vector<pair<int,int>> z;
	int e[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			e[i][j] = 0;
		}
	}
	z.push_back(make_pair(y1,x1));
	r[y1][x1] = '#';
	for (int i = 0; i < z.size(); i++) {
		int y = z[i].first;
		int x = z[i].second;
		static int dy[] = {1,0,-1,0};
		static int dx[] = {0,1,0,-1};
		for (int j = 0; j < 4; j++) {
			int uy = y+dy[j];
			int ux = x+dx[j];
			if (uy < 0 || ux < 0 || uy >= n || ux >= m || r[uy][ux] == '#') continue;
			z.push_back(make_pair(uy,ux));
			r[uy][ux] = '#';
			e[uy][ux] = e[y][x]+1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			r[i][j] = l[i][j];
		}
	}
	return e[y2][x2];
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> l[i][j];
			r[i][j] = l[i][j];
			if (l[i][j] == 'A') a = make_pair(i,j);
			else if (l[i][j] == 'B') b = make_pair(i,j);
			else if (l[i][j] == '*') v.push_back(make_pair(i,j));
		}
	}
	int path = 0;
	int min = 999999;
	int idx = 0;
	for (int i = 0; i < v.size(); i++) {
		int d = dist(a.first,a.second,v[i].first,v[i].second);
		if (d < min) {
			min = d;
			idx = i;
		}
	}
	path += min;
	int dx = v[idx].first;
	int dy = v[idx].second;
	l[dx][dy] = '.'; r[dx][dy] = '.';
	v.erase(v.begin() + idx);
	while (v.size() > 1) {
		min = 999999;
		idx = 0;
		for (int j = 0; j < v.size(); j++) {
			if (v[j].first != dx && v[j].second != dy) {
				int d = dist(dx,dy,v[j].first,v[j].second);
				if (d < min) {
					min = d;
					idx = j;
				}
			}
		}
		path += min;
		dx = v[idx].first;
		dy = v[idx].second;
		l[dx][dy] = '.'; r[dx][dy] = '.';
		v.erase(v.begin() + idx);
	}
	path += dist(dx,dy,v[0].first,v[0].second);
	path += dist(v[0].first,v[0].second,b.first,b.second);
	cout << path << "\n";
}

Test details

Test 1

Verdict:

input
84 87 2
##############################...

correct output
104

user output
126

Test 2

Verdict:

input
100 100 8
##############################...

correct output
264

user output
362

Test 3

Verdict: ACCEPTED

input
26 51 1
##############################...

correct output
48

user output
48

Test 4

Verdict:

input
100 100 8
##############################...

correct output
145

user output
197

Test 5

Verdict:

input
68 50 7
##############################...

correct output
88

user output
100

Test 6

Verdict:

input
100 100 8
##############################...

correct output
187

user output
205

Test 7

Verdict:

input
61 79 6
##############################...

correct output
149

user output
237

Test 8

Verdict:

input
100 100 8
##############################...

correct output
232

user output
384

Test 9

Verdict:

input
94 27 6
###########################
###########################
###########################
#############.#############
...

correct output
82

user output
112

Test 10

Verdict:

input
100 100 0
##############################...

correct output
30

user output
(empty)

Test 11

Verdict: ACCEPTED

input
65 100 6
######.#######################...

correct output
233

user output
233

Test 12

Verdict:

input
100 100 8
##############################...

correct output
209

user output
217

Test 13

Verdict:

input
75 18 3
##################
##################
##################
##################
...

correct output
72

user output
90

Test 14

Verdict:

input
100 100 8
##############################...

correct output
196

user output
248

Test 15

Verdict:

input
62 4 3
###.
####
####
####
...

correct output
44

user output
1000040

Test 16

Verdict:

input
100 100 8
##############################...

correct output
231

user output
271

Test 17

Verdict:

input
15 4 0
###.
.###
####
#.#.
...

correct output
4

user output
(empty)

Test 18

Verdict:

input
100 100 8
##############################...

correct output
300

user output
308

Test 19

Verdict: ACCEPTED

input
86 15 2
.########....##
#########......
#########......
#########......
...

correct output
88

user output
88

Test 20

Verdict:

input
100 100 8
##############################...

correct output
288

user output
334

Test 21

Verdict: ACCEPTED

input
51 90 3
.................................

correct output
103

user output
103

Test 22

Verdict:

input
100 100 8
.................................

correct output
352

user output
402

Test 23

Verdict:

input
22 91 4
.................................

correct output
128

user output
144

Test 24

Verdict:

input
100 100 8
.................................

correct output
317

user output
403

Test 25

Verdict:

input
49 42 6
.................................

correct output
175

user output
203