QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380094#5112. Where Am I?UFRJ#AC ✓726ms4492kbC++202.1kb2024-04-06 20:58:342024-04-06 20:58:35

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 20:58:35]
  • 评测
  • 测评结果:AC
  • 用时:726ms
  • 内存:4492kb
  • [2024-04-06 20:58:34]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    vector<int>dirx = {-1, 0, 1, 0};
    vector<int>diry = {0, 1, 0, -1};
    int n, m;
    cin>>m>>n;
    vector<string>s(n);
    for(int i=0;i<n;i++) cin>>s[i];
    int dx = 0, dy = 0;

    vector<vector<pair<int, int>>>v;
    {
        vector<pair<int, int>>cur;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) cur.emplace_back(i, j);
        }
        v.push_back(cur);
    }
    vector<vector<int>>ans(n, vector<int>(m, -1));
    int steps = 0, c = 0, k = 1, cnt = 0;
    while(!v.empty()){
        vector<vector<pair<int, int>>>nxt;
        for(auto& cur : v){
            vector<pair<int, int>>l, r;
            for(auto [x, y] : cur){
                int nx = x + dx;
                int ny = y + dy;
                int val = 0;
                if(0 <= nx && nx < n && 0 <= ny && ny < m && s[nx][ny] == 'X') val = 1;
                if(val) r.push_back({x, y});
                else l.push_back({x, y});
            }
            if(l.size() <= 1){
                if(!l.empty()){
                    auto [x, y] = l[0];
                    ans[x][y] = steps;
                }
            }
            else nxt.push_back(l);
            if(r.size() <= 1){
                if(!r.empty()){
                    auto [x, y] = r[0];
                    ans[x][y] = steps;
                }
            }
            else nxt.push_back(r);
        }
        swap(v, nxt);
        dx += dirx[c % 4];
        dy += diry[c % 4];
        steps++, cnt++;
        if(cnt == k) c++;
        if(cnt == k + k) c++, cnt = 0, k++;
    }
    int64_t tot = 0;
    int mx = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) tot += ans[i][j], mx = max(mx, ans[i][j]);
    }
    cout<<fixed<<setprecision(6);
    cout<<double(tot) / n / m<<"\n";
    cout<<mx<<"\n";
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<m;j++){
            if(ans[i][j] == mx) cout<<"("<<j+1<<","<<n-i<<") ";
        }
    }
    cout<<"\n";

    return 0;
}

詳細信息

Test #1:

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

input:

1 1
X

output:

0.000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 615ms
memory: 4216kb

input:

100 100
..X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X..
....................................................................................................
X............................................................................................

output:

4757.947100
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 565ms
memory: 4388kb

input:

100 100
X...................................................................................................
....................................................................................................
.............................................................................................

output:

19735.319900
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 558ms
memory: 4112kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19865.669900
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: 0
Accepted
time: 726ms
memory: 4212kb

input:

100 100
X...................................................................................................
.X..................................................................................................
..X..........................................................................................

output:

11855.639200
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

score: 0
Accepted
time: 724ms
memory: 4368kb

input:

100 100
...................................................................................................X
..................................................................................................X.
.............................................................................................

output:

11854.609800
39104
(1,99) (2,100) 

result:

ok correct!

Test #13:

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

input:

20 73
...........X........
.X..................
....................
X.....X........X....
......X........X....
....................
....................
.X..................
....................
...........X........
.X..................
X...................
.......X........X...
.X....X........X....
...

output:

50.097945
80
(7,6) (16,6) (20,12) (7,15) (16,15) (7,24) (16,24) (7,33) (16,33) (7,42) (16,42) (19,46) (12,47) (20,47) (7,51) (16,51) (12,56) (19,56) (7,60) (16,60) (20,65) (20,67) (7,69) (16,69) 

result:

ok correct!

Test #14:

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

input:

65 57
..............X..................................................
.................................................................
.........................................................X.......
........X.........X..............................................
..X.....X........................

output:

100.711201
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

score: 0
Accepted
time: 23ms
memory: 4012kb

input:

56 59
........................................................
........................................................
........................................................
........................................................
........................................................
X...........

output:

494.497881
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

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

input:

46 83
..........X...X.................X.............
..............................X...............
...X..........................................
.....................................X........
...X...........................X...X..........
.X............................................
...............

output:

122.545312
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

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

input:

51 57
........................X..........................
............................X......................
....................X.............X................
..................................................X
...................................................
.........................X...........

output:

103.487444
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

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

input:

64 91
................................................................
................................................................
................................................................
................................................................
.....................................

output:

480.572974
1215
(64,71) (63,91) 

result:

ok correct!

Test #19:

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

input:

75 40
.............................................X............X................
....................X..............................X.......................
...........................................X...........X...........X.......
...........................................X.....X......X............

output:

79.149333
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

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

input:

97 54
.............X...................................................................................
..................................X..............................................................
....X............................................................................................
...

output:

383.808324
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

score: 0
Accepted
time: 9ms
memory: 4084kb

input:

89 49
...............X...........X.............................................................
.............................................................X..X...........X............
.................................X.......................................................
...........................

output:

161.070167
520
(89,1) (2,41) 

result:

ok correct!

Test #22:

score: 0
Accepted
time: 10ms
memory: 4032kb

input:

80 55
.............................................................X..................
................................................................................
.................................................................XX.............
..............................................X.......

output:

176.083182
611
(80,2) (79,37) 

result:

ok correct!

Test #23:

score: 0
Accepted
time: 20ms
memory: 4052kb

input:

61 59
...........X.................................................
.............................................................
.......................................................X.....
.............................................................
...............................X.................

output:

291.706029
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

score: 0
Accepted
time: 10ms
memory: 4004kb

input:

48 74
....X.X.X.......................................
...............X.....X...X......................
..........................................X.....
................................................
................................................
.......X........................................
...

output:

152.161881
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

score: 0
Accepted
time: 25ms
memory: 4492kb

input:

100 96
.................................................................X..................................
.............................X......................................................................
..............................................................................................

output:

212.396250
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

score: 0
Accepted
time: 30ms
memory: 4204kb

input:

94 84
..............................................................................................
..............................................................................................
..............................................................................................
............

output:

357.121327
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

score: 0
Accepted
time: 15ms
memory: 4224kb

input:

86 80
...........................................................X..........X...............
......................................................................................
X.....................................................................................
....................................

output:

225.855523
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

score: 0
Accepted
time: 10ms
memory: 4012kb

input:

81 57
.X............X..................................................................
.................................................................................
.....................................X.........X.............X...................
...................................................

output:

139.734026
647
(24,1) (81,4) 

result:

ok correct!

Test #29:

score: 0
Accepted
time: 94ms
memory: 4072kb

input:

65 85
.................................................................
.................................................................
.................................................................
...................X.............................................
.................................

output:

738.974480
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

score: 0
Accepted
time: 149ms
memory: 4120kb

input:

76 98
............................................................................
............................................................................
............................................................................
..................................................................

output:

1550.390977
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

score: 0
Accepted
time: 46ms
memory: 4152kb

input:

62 67
..............................................................
..............................................................
.........................X....................................
...................................................X..........
.............................................

output:

648.650217
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

score: 0
Accepted
time: 17ms
memory: 4192kb

input:

50 98
..........................................X.......
.................................X...............X
..................................................
..................................................
.............................................X....
..........................................

output:

207.337755
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

score: 0
Accepted
time: 22ms
memory: 4204kb

input:

74 97
....................X.....................................................
..........................................................................
..........................................................................
................................X.......................................

output:

193.030231
1078
(74,70) (71,93) 

result:

ok correct!

Test #34:

score: 0
Accepted
time: 229ms
memory: 4408kb

input:

62 77
..............................................................
..............................................................
..............................................................
..............................................................
.............................................

output:

2021.069962
4937
(46,73) (8,77) 

result:

ok correct!

Test #35:

score: 0
Accepted
time: 7ms
memory: 3944kb

input:

47 74
...............................................
...............................................
...............................................
.....................X.........................
...............................................
............................................X..
.........

output:

142.153824
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

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

input:

47 71
...........X....X..............................
...............................................
...............................................
...........X...................................
.............................................X.
..X...........XX............X..................
.........

output:

102.814204
334
(44,4) (47,37) 

result:

ok correct!

Test #37:

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

input:

51 65
.........X..........X..............................
.................................X....X.........X..
................................................X..
...................................................
...................................................
.....................................

output:

81.669985
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

score: 0
Accepted
time: 15ms
memory: 4080kb

input:

40 93
.......X................................
........................................
........................................
........................................
.X......................................
..................X.....................
........................................
..........

output:

300.307527
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

score: 0
Accepted
time: 56ms
memory: 4288kb

input:

87 99
.......................................................................................
.......................................................................................
.......................................................................................
.................................

output:

474.068966
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

score: 0
Accepted
time: 199ms
memory: 4048kb

input:

46 94
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
...............

output:

2555.367484
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

score: 0
Accepted
time: 91ms
memory: 4100kb

input:

93 60
.............................................................................................
.............................................................................................
.............................................................................................
...............

output:

2389.200358
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

score: 0
Accepted
time: 18ms
memory: 4132kb

input:

98 61
.............................................X................................X...................
...................................................................X.............X................
..................................................................................X................

output:

225.089160
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

score: 0
Accepted
time: 21ms
memory: 4308kb

input:

94 95
..............................................................................................
.......................................................X......................................
............X................................................X.......................X........
............

output:

213.687570
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

score: 0
Accepted
time: 276ms
memory: 4236kb

input:

94 72
..............................................................................................
..............................................................................................
..............................................................................................
............

output:

1330.089539
4671
(60,71) (38,72) 

result:

ok correct!

Test #45:

score: 0
Accepted
time: 3ms
memory: 3940kb

input:

46 44
....X...X..............................X...X..
................................X..X......X...
..............X.........X.....................
......................X...........X...........
......................X.X........X.X...X......
.............X..........X.....................
.X.............

output:

67.354743
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

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

input:

65 51
.................................................................
.........................X.......................................
........X..............X.........................................
....X...............X............................................
.................................

output:

80.041026
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

score: 0
Accepted
time: 7ms
memory: 4200kb

input:

51 82
...................................................
...............X...........X.........X.............
..............................X....................
...................................................
...................................................
.......................X.............

output:

100.466045
360
(49,3) (51,62) 

result:

ok correct!

Test #48:

score: 0
Accepted
time: 25ms
memory: 4280kb

input:

87 60
.......................................................................................
........................................................................X..............
.......................................................................................
.................................

output:

302.789847
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

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

input:

53 44
...................................X.................
.....................................................
............................X....X...................
...X.................................................
.....................................................
....................X......

output:

150.346913
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

score: 0
Accepted
time: 105ms
memory: 4124kb

input:

94 97
..............................................................................................
.......................................X......................X...............................
..............................................................................................
............

output:

690.646414
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

score: 0
Accepted
time: 41ms
memory: 4092kb

input:

70 68
......................................................................
.....................X...........................X....................
........X...........................X...........................X.....
......................................................................
.............

output:

356.974580
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

score: 0
Accepted
time: 337ms
memory: 4276kb

input:

100 91
....................................................................................................
....................................................................................................
..............................................................................................

output:

1705.102198
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

score: 0
Accepted
time: 302ms
memory: 4260kb

input:

88 84
........................................................................................
........................................................................................
........................................................................................
..............................

output:

2976.142316
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

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

input:

48 44
................................................
................................................
..........X...........X.........................
...X............................................
...........................X....................
.........X......................................
...

output:

140.187973
466
(8,7) (1,20) 

result:

ok correct!

Test #55:

score: 0
Accepted
time: 21ms
memory: 4156kb

input:

98 60
......................................X.....X.....................................................
......................................X..............................X............................
............X......................................................X...............................

output:

179.279252
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

58 41
...............................X...............X..........
..X..................X....X...............................
..........................................................
.....................X.............................X......
..............................X.................X............

output:

75.129521
228
(2,1) (49,27) 

result:

ok correct!

Test #57:

score: 0
Accepted
time: 9ms
memory: 4024kb

input:

95 48
....X.......X.......................X..............X........................X...........X......
........X...............................X...............................X......................
........................XX...............................X.....................................
.........

output:

115.940570
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

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

input:

51 62
...................................................
..............................X.........X..........
................................................X..
.......................X...........................
..............................................X....
.....................................

output:

127.050285
432
(7,1) (51,6) 

result:

ok correct!

Test #59:

score: 0
Accepted
time: 22ms
memory: 4380kb

input:

86 98
.......X......X.......................................................................
......................................................................................
......................................................................................
....................................

output:

215.500949
732
(66,70) (68,72) 

result:

ok correct!

Test #60:

score: 0
Accepted
time: 27ms
memory: 4224kb

input:

91 94
...........................................................................................
...........................................................................................
...........................................................................................
.....................

output:

309.110358
1541
(78,1) (90,8) 

result:

ok correct!

Test #61:

score: 0
Accepted
time: 9ms
memory: 4072kb

input:

74 45
..........................................................................
..........................................................................
....X.............X..........................................X............
.X................X..........................X............X.............

output:

164.878078
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

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

input:

54 73
.....X.......X........................................
.............X........................................
...............X......................................
................................X.....................
..............................................X.......
......................

output:

106.012938
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

score: 0
Accepted
time: 59ms
memory: 4236kb

input:

91 56
...........................................................................................
..............................X.............................X..............................
.....................................................................X.....................
.....................

output:

423.714874
1455
(63,19) (24,20) 

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.000000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.666667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.666667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.666667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.333333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.666667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.666667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.666667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.250000
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.750000
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.750000
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.500000
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.750000
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.250000
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.000000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.500000
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.750000
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.000000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.750000
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.750000
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.500000
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.750000
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.250000
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.500000
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.250000
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.500000
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.500000
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.750000
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.750000
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.500000
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.500000
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.750000
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.500000
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.250000
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.250000
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.500000
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.666667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.000000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.000000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.000000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.333333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.000000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.666667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.750000
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.250000
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.000000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.250000
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.500000
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.250000
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.750000
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.000000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.500000
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.250000
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.250000
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.250000
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.500000
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

100 1
X...................................................................................................

output:

13274.590000
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

100 1
...................................................................................................X

output:

13076.630000
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

100 1
..................................................X.................................................

output:

3356.010000
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.500000
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

score: 0
Accepted
time: 3ms
memory: 3904kb

input:

100 1
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.

output:

3554.940000
9950
(49,1) (51,1) 

result:

ok correct!

Test #129:

score: 0
Accepted
time: 3ms
memory: 3928kb

input:

100 2
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X

output:

3451.070000
9751
(49,1) (51,1) 

result:

ok correct!

Test #130:

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

input:

1 100
X
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

12977.650000
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

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

input:

1 100
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X

output:

13175.610000
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

1 100
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

3306.030000
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

input:

1 100
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

output:

3406.500000
9850
(1,50) (1,51) 

result:

ok correct!

Test #134:

score: 0
Accepted
time: 3ms
memory: 4088kb

input:

1 100
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.

output:

3503.020000
9850
(1,50) (1,52) 

result:

ok correct!

Test #135:

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

input:

2 100
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
...

output:

3401.110000
9654
(2,49) (2,51) 

result:

ok correct!

Test #136:

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

input:

10 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

output:

58.080000
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

score: 0
Accepted
time: 432ms
memory: 4480kb

input:

100 100
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
....................................................................................................
.............................................................................................

output:

13878.927500
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

score: 0
Accepted
time: 426ms
memory: 4488kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

14059.272500
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

score: 0
Accepted
time: 441ms
memory: 4244kb

input:

100 100
X...................................................................................................
X...................................................................................................
X............................................................................................

output:

14132.282500
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

score: 0
Accepted
time: 429ms
memory: 4240kb

input:

100 100
...................................................................................................X
...................................................................................................X
.............................................................................................

output:

13951.432500
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

score: 0
Accepted
time: 565ms
memory: 4172kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19733.339900
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

score: 0
Accepted
time: 576ms
memory: 4216kb

input:

100 100
...................................................................................................X
....................................................................................................
.............................................................................................

output:

19601.009900
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

score: 0
Accepted
time: 157ms
memory: 4220kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

5001.489900
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

input:

20 20
.XX......XX.....XXXX
..X.....X..X....X...
.....X..............
X..XX.X..XX......XX.
X..........X........
...X..X............X
.X...X..........XXXX
.X...XX..XX....X....
X.X.XX...X.......X.X
XXXXX....X........X.
.X.XX.X..XX...X.X...
X.......X..XXX.....X
.X..X..X.X......X...
.........X....X...X.
...

output:

12.812500
31
(13,5) (15,18) 

result:

ok correct!

Test #145:

score: 0
Accepted
time: 3ms
memory: 4236kb

input:

50 50
..................................................
..................X...............X...............
..................................................
....X...X........................X........X..X....
.................X................................
..........................................

output:

60.830800
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

score: 0
Accepted
time: 27ms
memory: 4292kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

227.534900
1062
(96,95) (55,100) 

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed