#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
const int dx[] = { 0, 1, 0, -1 }, dy[] = { -1, 0, 1, 0 };
int C[12][39][12][39];
bool B[12][39][4], isX[12][39];
char A[25][80];
int H, W, Ans;
int main() {
scanf("%d%d ", &H, &W);
for(int i = 0; i < H; i++) fgets(A[i], INF, stdin);
H >>= 1; W >>= 1;
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
int y = i<<1|1, x = j<<1|1;
if(' ' == A[y-1][x]) B[i][j][0] = true;
if(' ' == A[y][x+1]) B[i][j][1] = true;
if(' ' == A[y+1][x]) B[i][j][2] = true;
if(' ' == A[y][x-1]) B[i][j][3] = true;
isX[i][j] = 'X' == A[y][x];
}
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
fill(C[i][j][0], C[i][j][11]+39, INF);
queue<int> PQ;
C[i][j][i][j] = 0;
PQ.push(i<<10|j);
for(int key, y, x, dst; !PQ.empty();) {
key = PQ.front(); PQ.pop();
y = key >> 10; x = key & ((1<<10)-1);
dst = C[i][j][y][x] + 1;
for(int dr = 0, ny, nx; dr < 4; dr++) if(B[y][x][dr]) {
ny = y+dy[dr]; nx = x+dx[dr];
if(C[i][j][ny][nx] <= dst) continue;
C[i][j][ny][nx] = dst;
PQ.push(ny<<10|nx);
}
}
}
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
if(!isX[i][j]) continue;
int mn = INF;
for(int y = 0; y < H; y++) for(int x = 0; x < W; x++) {
if(y == i && x == j) continue;
if(!isX[y][x]) continue;
upmin(mn, C[i][j][y][x]);
}
//Ans += mn*2-1;
Ans++;
}
cout << Ans << endl;
return 0;
}
Compilation message
connect.cpp: In function 'int main()':
connect.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d ", &H, &W);
~~~~~^~~~~~~~~~~~~~~~~
connect.cpp:23:34: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < H; i++) fgets(A[i], INF, stdin);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Wrong score! (6, expected 26) |
| 2 |
Incorrect |
2 ms |
376 KB |
Wrong score! (8, expected 40) |
| 3 |
Incorrect |
2 ms |
504 KB |
Wrong score! (24, expected 74) |
| 4 |
Incorrect |
2 ms |
376 KB |
Wrong score! (12, expected 28) |
| 5 |
Incorrect |
3 ms |
636 KB |
Wrong score! (80, expected 102) |
| 6 |
Incorrect |
4 ms |
636 KB |
Wrong score! (38, expected 112) |
| 7 |
Incorrect |
3 ms |
632 KB |
Wrong score! (20, expected 72) |
| 8 |
Incorrect |
3 ms |
760 KB |
Wrong score! (10, expected 94) |
| 9 |
Incorrect |
3 ms |
760 KB |
Wrong score! (30, expected 132) |
| 10 |
Incorrect |
5 ms |
888 KB |
Wrong score! (150, expected 208) |
| 11 |
Incorrect |
3 ms |
760 KB |
Wrong score! (16, expected 106) |
| 12 |
Incorrect |
6 ms |
888 KB |
Wrong score! (200, expected 268) |
| 13 |
Incorrect |
4 ms |
888 KB |
Wrong score! (162, expected 208) |
| 14 |
Incorrect |
3 ms |
1020 KB |
Wrong score! (80, expected 462) |
| 15 |
Incorrect |
3 ms |
888 KB |
Wrong score! (54, expected 422) |
| 16 |
Incorrect |
6 ms |
1148 KB |
Wrong score! (82, expected 664) |
| 17 |
Incorrect |
4 ms |
888 KB |
Wrong score! (42, expected 288) |
| 18 |
Incorrect |
8 ms |
1144 KB |
Wrong score! (70, expected 296) |
| 19 |
Incorrect |
9 ms |
1144 KB |
Wrong score! (90, expected 212) |
| 20 |
Incorrect |
9 ms |
1144 KB |
Wrong score! (300, expected 374) |
