QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#70724#5112. Where Am I?nvmdavaAC ✓971ms4120kbC++201.9kb2023-01-07 17:12:562023-01-07 17:12:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-07 17:12:58]
  • 评测
  • 测评结果:AC
  • 用时:971ms
  • 内存:4120kb
  • [2023-01-07 17:12:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second

int n, m;

char c[105][105];

bool is(int x, int y) {
    if(x < 1 || x > m || y < 1 || y > n) return 0;
    return c[x][y] == 'X';
}

vector<vector<pair<int, int> > > cur, pre;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    pre.push_back(vector<pair<int, int> >());

    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            cin>>c[i][j];
            pre[0].push_back({i, j});
        }
    }
    ll sum = 0;
    int x = 0, y = 0;
    int dir = 0, dis = 1, lef = 1;
    int i;
    for(i = 0; ; i++) {
        for(auto& vec : pre) {
            vector<pair<int, int> > t0, t1;
            for(auto& p : vec) {
                if(is(p.ff + x, p.ss + y)) t1.push_back(p);
                else t0.push_back(p);
            }
            if(t0.size() > 1) cur.push_back(t0);
            else if(t0.size() == 1) sum += i;
            if(t1.size() > 1) cur.push_back(t1);
            else if(t1.size() == 1) sum += i;
        }

        if(cur.empty()) break;
        swap(cur, pre);
        cur.clear();

        x += dx[dir];
        y += dy[dir];
        if(--lef == 0) {
            dis += dir & 1;
            lef = dis;
            dir = (dir + 1) % 4;
        }
    }

    cout<<setprecision(10)<<sum * 1.0 / n / m<<'\n';
    cout<<i<<'\n';
    vector<pair<int, int> > all;
    for(auto& vec : pre) {
        for(auto& p : vec) {
            all.push_back(p);
        }
    }
    sort(all.begin(), all.end(), [](const pair<int, int>& lhs, const pair<int, int>& rhs){
        return lhs.ff == rhs.ff ? lhs.ss < rhs.ss : lhs.ff > rhs.ff;
    });
    for(auto& p : all)
        cout<<"("<<p.ss<<','<<m + 1 - p.ff<<") ";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3760kb

input:

1 1
X

output:

0
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.111111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

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

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.9471
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 732ms
memory: 4044kb

input:

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

output:

19735.3199
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 714ms
memory: 3952kb

input:

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

output:

19865.6699
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

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

input:

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

output:

11855.6392
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

score: 0
Accepted
time: 971ms
memory: 3984kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

input:

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

output:

50.09794521
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: 3ms
memory: 3760kb

input:

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

output:

100.7112011
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

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

input:

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

output:

494.4978814
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

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

input:

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

output:

122.5453117
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

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

input:

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

output:

103.4874441
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

input:

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

output:

79.14933333
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

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

input:

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

output:

383.8083238
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

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

input:

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

output:

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

result:

ok correct!

Test #22:

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

291.7060295
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

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

input:

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

output:

152.1618806
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

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

input:

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

output:

212.39625
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

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

input:

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

output:

357.1213273
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

score: 0
Accepted
time: 26ms
memory: 3972kb

input:

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

output:

225.8555233
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

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

input:

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

output:

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

result:

ok correct!

Test #29:

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

input:

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

output:

738.9744796
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

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

input:

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

output:

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

result:

ok correct!

Test #31:

score: 0
Accepted
time: 60ms
memory: 3908kb

input:

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

output:

648.6502167
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

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

input:

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

output:

207.3377551
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

score: 0
Accepted
time: 28ms
memory: 4000kb

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

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

result:

ok correct!

Test #36:

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

input:

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

output:

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

result:

ok correct!

Test #37:

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

input:

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

output:

81.66998492
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

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

input:

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

output:

300.3075269
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

score: 0
Accepted
time: 77ms
memory: 4064kb

input:

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

output:

474.0689655
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

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

input:

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

output:

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

result:

ok correct!

Test #41:

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

input:

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

output:

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

result:

ok correct!

Test #42:

score: 0
Accepted
time: 24ms
memory: 3880kb

input:

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

output:

225.0891603
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

score: 0
Accepted
time: 29ms
memory: 3936kb

input:

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

output:

213.68757
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

score: 0
Accepted
time: 303ms
memory: 4040kb

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.35474308
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

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

input:

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

output:

80.04102564
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

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

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: 32ms
memory: 3924kb

input:

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

output:

302.7898467
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

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

input:

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

output:

150.3469125
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

score: 0
Accepted
time: 141ms
memory: 4044kb

input:

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

output:

690.6464137
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

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

input:

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

output:

356.9745798
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

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

input:

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

output:

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

result:

ok correct!

Test #53:

score: 0
Accepted
time: 434ms
memory: 3868kb

input:

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

output:

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

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

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

input:

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

output:

179.2792517
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

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

input:

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

output:

115.9405702
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

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

input:

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

output:

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

result:

ok correct!

Test #59:

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

input:

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

output:

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

result:

ok correct!

Test #60:

score: 0
Accepted
time: 40ms
memory: 3816kb

input:

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

output:

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

result:

ok correct!

Test #61:

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

input:

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

output:

164.8780781
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

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

input:

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

output:

106.0129376
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

score: 0
Accepted
time: 57ms
memory: 4040kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.6666666667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.6666666667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.6666666667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.333333333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.666666667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.6666666667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.666666667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.25
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.75
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

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

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.75
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.5
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

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

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.75
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.25
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.5
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.75
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.75
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.75
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.5
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.75
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.25
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.5
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.25
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.5
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.5
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.75
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.75
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.5
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.5
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.75
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.5
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.25
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.25
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.5
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.666666667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.333333333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.666666667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.75
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.25
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.25
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.5
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

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

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.25
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.75
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.5
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.25
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

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

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.25
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.25
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.5
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

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

output:

13274.59
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

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

output:

13076.63
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

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

output:

3356.01
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.5
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

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

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.94
9950
(49,1) (51,1) 

result:

ok correct!

Test #129:

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

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.07
9751
(49,1) (51,1) 

result:

ok correct!

Test #130:

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

input:

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

output:

12977.65
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

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

input:

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

output:

13175.61
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

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

output:

3306.03
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

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.5
9850
(1,50) (1,51) 

result:

ok correct!

Test #134:

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

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.02
9850
(1,50) (1,52) 

result:

ok correct!

Test #135:

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

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.11
9654
(2,49) (2,51) 

result:

ok correct!

Test #136:

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

input:

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

output:

58.08
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

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

input:

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

output:

13878.9275
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

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

input:

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

output:

14059.2725
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

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

input:

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

output:

14132.2825
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

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

input:

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

output:

13951.4325
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

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

input:

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

output:

19733.3399
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

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

input:

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

output:

19601.0099
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

score: 0
Accepted
time: 194ms
memory: 3952kb

input:

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

output:

5001.4899
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

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.8125
31
(13,5) (15,18) 

result:

ok correct!

Test #145:

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

input:

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

output:

60.8308
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed