QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#370373#3172. Tomb RaiderDjangle162857AC ✓994ms94260kbC++147.5kb2024-03-29 02:42:042024-03-29 02:42:05

Judging History

This is the latest submission verdict.

  • [2024-03-29 02:42:05]
  • Judged
  • Verdict: AC
  • Time: 994ms
  • Memory: 94260kb
  • [2024-03-29 02:42:04]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " == " << x << endl
#define FINISH cerr << "FINISH!!!!" << endl;
#define el '\n'
#define fir first
#define sec second
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
const int N = 550;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
void solve()
{
	int h, w, tot = 0;
	cin >> h >> w;
	vector<vector<char>> ch(h + 2, vector<char>(w + 2, '*'));
	vector<vector<int>> idx(h + 2, vector<int>(w + 2, 0));
	vector<int> col((h + 2) * (w + 2), 0);
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> ch[i][j];
			if (ch[i][j] == 'V' || ch[i][j] == 'H') {
				tot++;
				idx[i][j] = tot;
				col[tot] = (ch[i][j] == 'H') ? 1 : 0;
			}
		}
	}
	/*for (int i = 0; i <= h + 1; i++) {
		for (int j = 0; j <= w + 1; j++) {
			cout << ch[i][j];
		}
		cout << endl;
	}*/
	vector<vector<vector<int>>> edge(2, vector<vector<int>>(tot + 3));
	function<PII(int, int, int, int)> search = [&](int x, int y, int dx,
												   int dy) {
		int nowx = x, nowy = y, cnt = 0;
		// cout << x << " " << y << " " << dx << " " << dy << endl;
		while (1) {
			nowx += dx, nowy += dy;
			// cout << nowx << " " << nowy << endl;
			if (ch[nowx][nowy] == '#')
				break;
			if (ch[nowx][nowy] == '\\') {
				swap(dx, dy);
				// nowx += dx, nowy += dy;
				cnt++;
			}
			else if (ch[nowx][nowy] == '/') {
				swap(dx, dy);
				dx = -dx, dy = -dy;
				// nowx += dx, nowy += dy;
				cnt++;
			}
			else if (ch[nowx][nowy] == '*') {
				dx = -dx, dy = -dy;
				// nowx += dx, nowy += dy;
			}
			if (ch[nowx][nowy] == 'H' || ch[nowx][nowy] == 'V') {
				// cout << nowx << " " << nowy << endl;
				if (cnt % 2 == 1) {
					// edge1[idx[x][y]].push_back(idx[nowx][nowy]);
					// edge1[idx[nowx][nowy]].push_back(idx[x][y]);
					return PII(idx[nowx][nowy], 1);
					// cout << x << " " << y << " " << nowx << " " << nowy << "
					// "
					// 	 << "1" << endl;
				}
				else {
					// edge0[idx[x][y]].push_back(idx[nowx][nowy]);
					// edge0[idx[nowx][nowy]].push_back(idx[x][y]);
					return PII(idx[nowx][nowy], 0);
					// cout << x << " " << y << " " << nowx << " " << nowy << "
					// "
					// 	 << "0" << endl;
				}
			}
		}
		return PII(-1, -1);
		// cout << "FINISH" << endl;
	};
	vector<vector<int>> prohibit(tot + 3, vector<int>(2, 0));
	function<void(int, int)> dfs = [&](int x, int y) {
		int dx, dy;
		PII res1 = search(x, y, 1, 0), res2 = search(x, y, -1, 0);
		if (res1.fir != -1 && res2.fir != -1) {
			edge[res1.sec][idx[x][y]].push_back(res1.fir);
			edge[res1.sec][res1.fir].push_back(idx[x][y]);
			edge[res2.sec][idx[x][y]].push_back(res2.fir);
			edge[res2.sec][res2.fir].push_back(idx[x][y]);
			/*cout << idx[x][y] << " " << res1.fir << endl;
			cout << x << " " << y << " " << place[res1.fir].fir << " "
				 << place[res1.fir].sec << " " << res1.sec << endl;
			cout << idx[x][y] << " " << res2.fir << endl;
			cout << x << " " << y << " " << place[res2.fir].fir << " "
				 << place[res2.fir].sec << " " << res2.sec << endl;*/
			prohibit[idx[x][y]][0] = 1;
		}
		res1 = search(x, y, 0, 1), res2 = search(x, y, 0, -1);
		if (res1.fir != -1 && res2.fir != -1) {
			edge[res1.sec][idx[x][y]].push_back(res1.fir);
			edge[res1.sec][res1.fir].push_back(idx[x][y]);
			edge[res2.sec][idx[x][y]].push_back(res2.fir);
			edge[res2.sec][res2.fir].push_back(idx[x][y]);
			/*cout << idx[x][y] << " " << res1.fir << endl;
			cout << x << " " << y << " " << place[res1.fir].fir << " "
				 << place[res1.fir].sec << " " << res1.sec << endl;
			cout << idx[x][y] << " " << res2.fir << endl;
			cout << x << " " << y << " " << place[res2.fir].fir << " "
				 << place[res2.fir].sec << " " << res2.sec << endl;*/
			prohibit[idx[x][y]][1] = 1;
		}
	};
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (ch[i][j] == 'H' || ch[i][j] == 'V') {
				// cout << i << " " << j << endl;
				dfs(i, j);

				if (prohibit[idx[i][j]][0] == 0 &&
					prohibit[idx[i][j]][1] == 0) {
					cout << "-1" << endl;
					return;
				}
			}
		}
	}
	// FINISH
	vector<vector<int>> block(tot + 3);
	vector<int> vis(tot + 3, 0);
	function<void(int, int)> find = [&](int x, int res) {
		if (vis[x])
			return;
		vis[x] = res;
		block[res].push_back(x);
		for (auto to : edge[0][x]) {
			if (vis[to])
				continue;
			find(to, res);
		}
	};
	int now = 0;
	for (int i = 1; i <= tot; i++) {
		if (!vis[i])
			find(i, ++now);
	}
	// 0->V 1->H
	/*for (int i = 1; i <= tot; i++) {
		cout << col[i] << endl;
		cout << prohibit[i][0] << " " << prohibit[i][1] << endl;
	}*/
	int ans = 0;
	int cnt = 0;
	vector<vector<int>> val(tot + 3, vector<int>(2, 0));
	for (int i = 1; i <= now; i++) {
		// debug(i);
		int cnt0 = 0, cnt1 = 0;
		for (auto x : block[i]) {
			// cout << x << " ";
			if (prohibit[x][0] == 0) {
				cnt0 = inf;
			}
			if (prohibit[x][1] == 0) {
				cnt1 = inf;
			}
			if (cnt0 <= inf && col[x] == 1)
				cnt0++;
			if (cnt1 <= inf && col[x] == 0)
				cnt1++;
		}
		val[i][0] = cnt0;
		val[i][1] = cnt1;
		if (cnt0 <= inf)
			cnt += cnt0;
		if (cnt1 <= inf)
			cnt += cnt1;
		/*cout << endl;
		cout << val[i][0] << " " << val[i][1] << endl;*/
	}
	// cout << cnt << endl;
	// assert(cnt <= tot * 2);
	/*for (int i = 1; i <= tot; i++) {
		cout << vis[i] << " ";
	}
	cout << endl;*/
	vector<vector<int>> edge1(tot + 3);

	for (int i = 1; i <= now; i++) {
		vector<int> fl(tot + 3, 0);
		for (auto x : block[i]) {
			cnt++;
			for (auto to : edge[1][x]) {
				if (vis[x] != vis[to] && fl[vis[to]] == 0) {
					fl[vis[to]] = 1;
					edge1[i].push_back(vis[to]);
					// edge1[vis[to]].push_back(i);
				}
				if (vis[x] == vis[to]) {
					cout << "-1" << endl;
					return;
				}
			}
		}
	}

	/*FINISH
	for (int i = 1; i <= now; i++) {
		for (auto to : edge1[i]) {
			cout << "EDGE" << i << " " << to << endl;
		}
	}*/
	int ans1 = 0, ans2 = 0;
	vector<int> las, lt;
	vector<int> tmp(tot + 3, 0);
	function<int(int, int)> getcol = [&](int x, int c) -> int {
		// cout << "getcol   " << x << endl;
		vis[x] = 1, col[x] = c;
		las.push_back(x);
		int sum = val[x][c], flag = 0;
		tmp[x]++;
		for (int to : edge1[x]) {
			if (vis[to]) {
				// cout << x << " " << to << endl;
				// cout << col[x] << " " << col[to] << endl;
				if (col[to] == col[x]) {
					flag = 1;
				}
				continue;
			}
			int noww = getcol(to, c ^ 1);
			if (noww == -1)
				flag = 1;
			sum += noww;
		}
		if (flag != 1)
			return sum;
		return -1;
	};
	for (int i = 1; i <= now; i++) {
		vis[i] = col[i] = 0;
	}
	for (int i = 1; i <= now; i++) {
		int sum1 = 0, sum2 = 0;
		// debug(i);
		if (vis[i])
			continue;
		sum1 = getcol(i, 0);
		if (sum1 == -1) {
			// cout << i << endl;
			cout << "-1" << endl;
			return;
		}
		// cout << "LAS" << endl;
		for (auto x : las) {
			// cout << x << " ";
			vis[x] = col[x] = 0;
			lt.push_back(x);
		}
		// cout << endl;
		las.clear();
		sum2 = getcol(i, 1);
		// cout << sum1 << " " << sum2 << endl;
		ans1 += min(sum1, sum2);
		las.clear();
		/*cout << "VIS" << endl;
		for (int j = 1; j <= 3; j++)
			cout << vis[j] << " ";
		cout << endl;
		cout << ans1 << endl;*/
	}
	if (ans1 >= inf)
		ans1 = -1;
	cout << ans1 << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3676kb

input:

5 5
/.V.\
./.V.
..#..
.V.#.
\.V./

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

2 5
V...\
H...V

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

2 2
VV
VV

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

4 3
/.\
H..
\H.
..H

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

5 5
.....
.H.V.
.....
.H.H.
.....

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

4 12
./.....\/.\.
.V\#/V./.#V\
/H/#\H../#H/
\........./.

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

4 12
./.....\/.\.
.V\#/V./.#V\
/H/#\H../#H/
\\......../.

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

2 2
#H
V#

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

2 2
V.
\#

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

2 2
V#
\#

output:

-1

result:

ok single line: '-1'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

3 5
V.#.\
./\..
\/\./

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

2 2
/#
H/

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

1 1
H

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

2 1
V
#

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3784kb

input:

1 2
#H

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

5 5
V\#VH
H/#\/
#####
/\#/V
VH#\H

output:

4

result:

ok single line: '4'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

4 5
/.\/#
.///\
.\V/.
\.../

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

3 3
/\#
\.\
#\H

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

3 3
/\#
\V\
#\/

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

4 4
/..\
./\.
.H./
\./#

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

4 6
/.\...
....H\
..HHH.
\..../

output:

-1

result:

ok single line: '-1'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

4 4
/\/\
\/H/
/H/\
\/\/

output:

-1

result:

ok single line: '-1'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

6 6
../\..
..HH..
/H..V\
\H..H/
..HV..
..\/..

output:

2

result:

ok single line: '2'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

6 6
../\..
..HH#.
/H..V\
\H..H/
..HV#.
..\/..

output:

4

result:

ok single line: '4'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

6 6
../\..
..HH..
/H..V\
\H#.H/
..HV..
..\/..

output:

4

result:

ok single line: '4'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

3 2
V\
V.
\/

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

5 4
V.V\
/../
\..\
/../
V.V.

output:

-1

result:

ok single line: '-1'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

3 2
V#
..
VV

output:

-1

result:

ok single line: '-1'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

4 4
#V..
.VV.
..VV
...#

output:

-1

result:

ok single line: '-1'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

4 5
#V...
.VV\.
...VV
#...V

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

4 7
#V.../\
.VV..//
....//.
...VV.#

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

4 4
/\.H
\/#.
##//
V./V

output:

2

result:

ok single line: '2'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

4 4
H/\V
/VH\
\HH/
V\/H

output:

1

result:

ok single line: '1'

Test #34:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

2 4
/V\\
\\.V

output:

1

result:

ok single line: '1'

Test #35:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

2 3
/V\
\.V

output:

-1

result:

ok single line: '-1'

Test #36:

score: 0
Accepted
time: 6ms
memory: 9000kb

input:

500 500
V...V.....H.......H.......V.......................H...V.H.......V.....H.V...V.........V.......H.........V...................H.....................H.H.................................V.................H.......V.........V...V.H.V.H.....H.......V.........V.V.V.....V...................H.......V....

output:

6264

result:

ok single line: '6264'

Test #37:

score: 0
Accepted
time: 0ms
memory: 5412kb

input:

500 500
.......................................................................................................................................................................................................................................................................................................

output:

297

result:

ok single line: '297'

Test #38:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

22 22
V/VVHVVHHHHHVVVVHVHHH\
HV/HHVHHHVVHVVHHHVVV\V
HHV/HHVVHHHHVHVVHVH\HH
VVHV/VHVHHVHHHHVHV\VVH
VVVVH/HHVHVVHHHVV\VHVV
VVHHVH/HVHHHVVVV\VVHHV
VHHHVVV/VVVVHVV\HHVVHH
HHVHVVVV/VVVHH\HHVHHHH
VVHHHHVVV/HVH\VVHVHVHV
HVHVHHHHHH/V\HVVHHHVVH
...........\HVVHHHVVVH
VVHVVVVHVV\/VVVVVHHVVV
HVVVVVVVV\HH/VHVVV...

output:

201

result:

ok single line: '201'

Test #39:

score: 0
Accepted
time: 80ms
memory: 76320kb

input:

500 500
V/HHVHHHVVVVVHVVVVHVVHHVVHVHVVHVHHHHHVHHVVHHVHVHHVVVHVVVVHHVHHHVVHHHVHVVVHHVVHHHHHVVVHVHVHVVHVHVVVVVVVVHVVVVVVVVHHHVVVVHVHHVHVVHHHHVHVHVHHVHVVHHVHHVVVVHVVVHHHHHVVHVVHVVHVHVVVHHVHHHVHHVHVVVHVVHVVHHVVVVHVVHVHHVVHHHHHVVVHVVVVVVHVVVVHHHHVVHVVVHHHHHVHVVHHHHHVVHVVVHHHVHVVVVHVVVHVHHVVHVHHVHHVHVVVHV...

output:

124323

result:

ok single line: '124323'

Test #40:

score: 0
Accepted
time: 65ms
memory: 62760kb

input:

377 497
V/HVVHHHVVVVVHHVVVHHHHVHVHHHVVVVHVVVHVHHHVHHHHVHVHVVVHHVHHVHHHVHVHVHVHHHHHVVHVVVVHVVHHHVVHVHHVVHVHVHVVHVVVVHVHVHVVHVHHVVHVHVHVHVVHVVHVVVHHHHHHHVVHHVVHVVVHVVVVHHVVHVVHHVVVVHVHHVHHVVHVVVHHVHVHHVHHHVVVVVHVHVHVVVHHHHHHHHVVVHHVVVHHVHHHVHHHVVHHVVHHVVHVHVHVVVVHVHHVHVVHHVHHVVHVHHHVVHHVHVVVHVHVVHHHHH...

output:

93082

result:

ok single line: '93082'

Test #41:

score: 0
Accepted
time: 108ms
memory: 94260kb

input:

500 500
HHHHVVVHHHHHVHHVHVHHVVHVVHVHHHHHHVVVVVVVVVVHVHVVHHVVVVHHVVHVVVVVHVHVVHHVHVHVVHHHHVHHVVHHHVHVVVHHVHVVHVVVVVHHHHHHVHHHVVHVVVHVHHHVHHVVHVHVVHVHVVVVHVHVHVHVHHHHVVVVVVVVVVHVVHHHHHHHHHHHVHHVHHHVVVVVHHHVHVVHHVVVVHVVHVVVVVVVVVHHVVHVVHHHHHHVHVVHHHHHVHHHHVHHVVVVHHHHVVHVVHHHVVHVVHVHHHVVVVVVVVHHVVVVHVHV...

output:

124838

result:

ok single line: '124838'

Test #42:

score: 0
Accepted
time: 74ms
memory: 76432kb

input:

500 500
HV..VHVVHV..V.VVV.VHH.V...VVH.HV.VVVH.VV.VVHVHHHV.HHHVVVVHHHVV.V.V.H.HHVV.H.VVVH...VV.H.VVHHVVVHHV.HV.VV..HHH.VHVV..VVHVVVHHHHVV..H.HV.VH.HHV.V.V..VHH.H.HVVHHHHHVHVVH.VHV..VHVVHHHVHH.HHHV.VHVHHV.HHVVVVH..HV.VHVVVVVHVVHHVVH.V.HVHVVHVVVH.V.HH.VVV.VV.VV...H..VHV.HVVHVVVVV.H.V.H.VV.VHVVHH.HV.VV....

output:

99969

result:

ok single line: '99969'

Test #43:

score: 0
Accepted
time: 8ms
memory: 7456kb

input:

500 500
.............................H...................................................................H..............V........................................H........H...................................V...........................H....V...............................V..H............................

output:

3492

result:

ok single line: '3492'

Test #44:

score: 0
Accepted
time: 6ms
memory: 6092kb

input:

500 499
...........................H.........H..................................................................................................................V........................................................................................................H...............................V.....

output:

1178

result:

ok single line: '1178'

Test #45:

score: 0
Accepted
time: 2ms
memory: 5816kb

input:

500 500
...........................................................H........................................................................................................................................................................................V..........................V.......................

output:

307

result:

ok single line: '307'

Test #46:

score: 0
Accepted
time: 42ms
memory: 26812kb

input:

500 500
/.H.......VHV..H.HVH....V..V.V.H.V........V...V..H.........V.H...VVV....V..V.H...V........H.....HV...VVHV..V............V..VV....V.H....V.HV...H.......V........HHV..V....V...V.......HVH...V...HH...V...V.HH...V...VV..V....H.H......V....H.....V..V..V....V..HH...H...V.H..V.HV..HH.H..H...HVH..HH...

output:

37291

result:

ok single line: '37291'

Test #47:

score: 0
Accepted
time: 6ms
memory: 6352kb

input:

500 500
/...............................................................................................H......................................................................................................................................................................................................

output:

1202

result:

ok single line: '1202'

Test #48:

score: 0
Accepted
time: 5ms
memory: 5772kb

input:

499 499
.....................#....#...#...#.....#..................#.................#....#..#.................................#..#...............#..#.#.#.....#......#.............#..#.......#...#................................#..#...#..#.#.................#...#........#....#......#....#.....#.#......

output:

282

result:

ok single line: '282'

Test #49:

score: 0
Accepted
time: 187ms
memory: 24920kb

input:

499 499
..............#....#...##..#......#.......#.#...#.#......#...............#....................#...............#...........#.......#....#........#......#......#.........#.#.#...#.....#....#.#.#..#..........#.........##...#......#..#..#.......#.....#...........#.#...#............#...#...#..#.....

output:

29350

result:

ok single line: '29350'

Test #50:

score: 0
Accepted
time: 6ms
memory: 5976kb

input:

500 500
/V.....................................................................................................................................................................................................................................................................................................

output:

734

result:

ok single line: '734'

Test #51:

score: 0
Accepted
time: 6ms
memory: 5744kb

input:

500 500
/......................................................................................................................................................................................................................................................................................................

output:

288

result:

ok single line: '288'

Test #52:

score: 0
Accepted
time: 47ms
memory: 44072kb

input:

500 500
VHHVHHVVVHVVVVVHVHVHHVVHHHHHHVVHVVHHHVHVVVHHHVHVVHHVVVHHHHVHVVVHVHVVHHHVVVVHHVHHHVVHHVHHVHHVHVHVVHHVHHVHVVVVHVVHVHHVHVVVVHHHHHHVVHHHVHHVVVHHVHVVHVHVHHVHHHVHVVVVHVHVVHVHVVVVVVVHHHHHHHHHVVHVVHHHHVHVVHVHVHVVHVHHHVHHHHHHVHVVVVVHHVVHHHVHVVHHHHVVVVHHHHHHHH\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\...

output:

62231

result:

ok single line: '62231'

Test #53:

score: 0
Accepted
time: 43ms
memory: 32108kb

input:

498 498
HVVHHVVHVVHHVVHHHHHHHHVHHHVHHVVHHVVHHHHHVVHHHVHVVHVHHVHVHVVVVHHHHHVHVHHVHVHHVHHHHVHHVVVHHVHHHVHVHVVVHHVHHHHVVVHHHVHVHVHHVHHVVVVVVHHVVVHHVHHHHHVVVHVHVVVHHHHHVHVVHVHVHH.................................................................................................................................

output:

41225

result:

ok single line: '41225'

Test #54:

score: 0
Accepted
time: 994ms
memory: 59676kb

input:

500 500
V/H\V/V/V\V/H\V/V/H/V/V\V\H\H/H\V\H\V\H/H/H/V/H/V\V/H\V\H\H\V/H/H\H\H/H/H/H\H/H/V\H\H\V/H\H\H\H\V\V/V/H/H/V/H\H\H/H\V/V/H/V/H/H\V\V\V/H\H\V/H\V\H/V/H/V/V/H\H/V/H\H/H\H/V\H\H\H\V/V\V/V/V/V\H\V/V/V\H\H\V/H\V/V\V/H\V/H\V\V/V/H/V\V/V\H/H\V\H\V\V\V/H\H\H/V\V/H/H\H\V/V\H/H/H/V/H/V/H/H/V/V\H/V\H/V\...

output:

62463

result:

ok single line: '62463'

Test #55:

score: 0
Accepted
time: 284ms
memory: 44360kb

input:

500 500
VV\\VV//HV\\VH//VH\\VH//HV\\VV\\VH//HV\\VV//VV//VH//HH//HV//VV//VH\\VH//VH//HH//VV\\VV\\VH//VV\\HH\\HV//HH\\HH\\VV\\HH\\HV//VV\\HV\\VV\\HV//VH\\VV//VV\\HV\\HH\\VV//HH\\HH//HH//VH\\VH//HH//VV\\HV\\VV//VH//HH\\HH//VH//HV\\HH\\HV//VV\\VV//HH\\VH//HV\\HH\\VH//HH//VV//VV\\VH\\VV\\HV\\VV\\VH\\VV\\...

output:

62355

result:

ok single line: '62355'

Test #56:

score: 0
Accepted
time: 31ms
memory: 38772kb

input:

500 500
VHVHHVVHVHHVVVHVHHVVVHHHHHVVHHVHVVHHVVHHVHVHHHHHHH\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\VHHVHHHVHHVVVVHHVVHHVHHVHVVVHHVVHVVHVHHVHHHVHHHVHH\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\VHVHHHVHVHVHHHVHVVVHVHHHVVVHVVVVVHHVVVHVHVVHVHHVVV\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\...

output:

62448

result:

ok single line: '62448'

Test #57:

score: 0
Accepted
time: 0ms
memory: 5676kb

input:

500 500
VV.....................................................................................................................................................................................................................................................................................................

output:

498

result:

ok single line: '498'

Test #58:

score: 0
Accepted
time: 2ms
memory: 5732kb

input:

500 500
HV.....................................................................................................................................................................................................................................................................................................

output:

-1

result:

ok single line: '-1'

Test #59:

score: 0
Accepted
time: 13ms
memory: 12240kb

input:

500 500
HHVVHVVVVHHHVHHVVVHHVVHHVVVHVVVVHHHHVVVHVVHVVVVVVV.....................................................................................................................................................................................................................................................

output:

12462

result:

ok single line: '12462'

Test #60:

score: 0
Accepted
time: 11ms
memory: 12348kb

input:

500 500
VHVHVVVVVVVHHHVHVHVHVHVHHHHHHVHVHHHHVVVVVVHVVVHVHH.....................................................................................................................................................................................................................................................

output:

-1

result:

ok single line: '-1'

Test #61:

score: 0
Accepted
time: 0ms
memory: 5452kb

input:

500 500
#HH/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...

output:

241

result:

ok single line: '241'

Test #62:

score: 0
Accepted
time: 4ms
memory: 5400kb

input:

500 500
#VH/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...

output:

-1

result:

ok single line: '-1'

Test #63:

score: 0
Accepted
time: 5ms
memory: 5448kb

input:

500 500
.......................................................................................................................................................................................................................................................................................................

output:

0

result:

ok single line: '0'

Test #64:

score: 0
Accepted
time: 4ms
memory: 5472kb

input:

499 499
/........................................................................................................................................................................................................................................................\.............................................

output:

-1

result:

ok single line: '-1'

Test #65:

score: 0
Accepted
time: 4ms
memory: 5480kb

input:

500 500
H/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...

output:

244

result:

ok single line: '244'

Test #66:

score: 0
Accepted
time: 5ms
memory: 5484kb

input:

500 500
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...

output:

2

result:

ok single line: '2'

Test #67:

score: 0
Accepted
time: 5ms
memory: 5580kb

input:

500 500
./\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...

output:

239

result:

ok single line: '239'

Test #68:

score: 0
Accepted
time: 5ms
memory: 5464kb

input:

500 500
./\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...

output:

228

result:

ok single line: '228'

Test #69:

score: 0
Accepted
time: 2ms
memory: 5508kb

input:

500 500
./\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...

output:

240

result:

ok single line: '240'

Test #70:

score: 0
Accepted
time: 88ms
memory: 82148kb

input:

500 500
HHHHVVVVVHHHVHVHHHVHHHHHVVVHVHVHHHVVHHVHHHHHVHHHVVVVVHVVVVVVVVVVVHHVVVVHVVVVVHVHHVVHVHHVHHHVVHVHHHVHHHVVVVVVVVHHVVVVVVVHHVVHHHHHHHHVVVVVVVVVHHHVVVHVVHVHVVVVHHVHVHHVVVHHHVVHHHVHVHVHHHHVHVHVHHVVVVHHHVVHHHVHHHHVHHVVHVHVHVHVVVHHVHHHVVVVVVVHHVVHVVVHVHVHH/\HHHHVHVVHVHHHVHVVHHHHHHVVHHHVHHHVVVVHHVHV...

output:

-1

result:

ok single line: '-1'

Test #71:

score: 0
Accepted
time: 45ms
memory: 60160kb

input:

500 500
VVHV/\VVVHVVHH/\HHHVVVHV/\VHHVVHHH/\HVVVVVHH/\HVHHVVVV/\HVVHVHVV/\VVVHHHVV/\HVVHHVHV/\VHHHHHHH/\VVVVHHHH/\HHHHHVVV/\VHVVVHHH/\VHVHHHVV/\VVHHVVVV/\VHVHVVHV/\HHHVVVVH/\HHVVVVVH/\VVVVVVVH/\VVHHHVVH/\VHVHHHHH/\HVHHVVHH/\VHVVHHHH/\HVHVHHHV/\HVHHVVHV/\VHVVVVVV/\VVHVHVHV/\VVHHVHVH/\VHHHVHHH/\HHVHHV...

output:

-1

result:

ok single line: '-1'

Test #72:

score: 0
Accepted
time: 5ms
memory: 5548kb

input:

500 500
.......................................................................................................................................................................................................................................................................................................

output:

161

result:

ok single line: '161'

Test #73:

score: 0
Accepted
time: 4ms
memory: 5508kb

input:

500 500
.......................................................................................................................................................................................................................................................................................................

output:

-1

result:

ok single line: '-1'