#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 80, INF = 1e9;
const ll mod = 1e9 + 7;
int r, c, n, m, dp[12][40][(1 << 12)][2], pr[12][40][(1 << 12)][2], cntX;
string s[N];
void inputs(){
scanf("%d %d\n", &r, &c);
for(int i = 0;i < r;i++)
getline(cin, s[i]), scanf("\n");
for(int i = 0;i < r;i++)
for(int j = 0;j < c;j++)
cntX += (s[i][j] == 'X');
n = r / 2, m = c / 2;
}
bool good(int x, int y, int tp){
bool res = 1;
if(tp <= 4 && s[x][y] != 'X')
res = 0;
if(tp == 1 || tp == 9 || tp == 10 || tp == 11){
if(s[x][y - 1] == '|')
res = 0;
}
if(tp == 2 || tp == 7 || tp == 8 || tp == 11){
if(s[x - 1][y] == '-')
res = 0;
}
if(tp == 3 || tp == 6 || tp == 7 || tp == 10){
if(s[x + 1][y] == '-')
res = 0;
}
if(tp == 4 || tp == 6 || tp == 8 || tp == 9){
if(s[x][y + 1] == '|')
res = 0;
}
return res;
}
int main () {
inputs();
for(int j = 0;j < m;j++)
for(int i = 0;i < n;i++)
for(int mask = 0;mask < (1 << n);mask++)
dp[i][j][mask][0] = dp[i][j][mask][1] = INF;
for(int i = 0, j = 0;i < n;i++){
for(int mask = 0;mask < (1 << n);mask++){
if(s[i * 2 + 1][j * 2 + 1] == 'X'){
if(!((mask >> i) & 1)){
int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][1]: INF);
if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 2)){
dp[i][j][mask][0] = val;
pr[i][j][mask][0] = 2;
}
val = (i ? dp[i - 1][j][mask][0]: INF) + 1;
if(val > INF && mask == 0)
val = 1;
if(dp[i][j][mask][1] > val && good(i * 2 + 1, j * 2 + 1, 3)){
dp[i][j][mask][1] = val;
pr[i][j][mask][1] = 3;
}
if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 4)){
dp[i][j][newmask][0] = val;
pr[i][j][newmask][0] = 4;
}
}
}
else{
if((mask >> i) & 1)
continue;
int val = (i ? dp[i - 1][j][mask][0]: INF);
if(mask == 0 && i == 0)
val = 0;
if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 5)){
dp[i][j][mask][0] = val;
pr[i][j][mask][0] = 5;
}
int newmask = mask ^ (1 << i);
if(dp[i][j][newmask][1] > val + 3 && good(i * 2 + 1, j * 2 + 1, 6)){
dp[i][j][newmask][1] = val + 3;
pr[i][j][newmask][1] = 6;
}
val = (i ? dp[i - 1][j][mask][1]: INF);
if(dp[i][j][mask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 7)){
dp[i][j][mask][1] = val + 2;
pr[i][j][mask][1] = 7;
}
if(dp[i][j][newmask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 8)){
dp[i][j][newmask][0] = val + 2;
pr[i][j][newmask][0] = 8;
}
}
}
}
for(int j = 1;j < m;j++){
for(int i = 0;i < n;i++){
for(int mask = 0;mask < (1 << n);mask++){
if(s[i * 2 + 1][j * 2 + 1] == 'X'){
if(((mask >> i) & 1) && j){
int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 1)){
dp[i][j][newmask][0] = val;
pr[i][j][newmask][0] = 1;
}
}
if(!((mask >> i) & 1)){
int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][1]: INF);
if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 2)){
dp[i][j][mask][0] = val;
pr[i][j][mask][0] = 2;
}
val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]) + 1;
if(dp[i][j][mask][1] > val && good(i * 2 + 1, j * 2 + 1, 3)){
dp[i][j][mask][1] = val;
pr[i][j][mask][1] = 3;
}
if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 4)){
dp[i][j][newmask][0] = val;
pr[i][j][newmask][0] = 4;
}
}
}
else{
if((mask >> i) & 1){
int val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
if(dp[i][j][mask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 9)){
dp[i][j][mask][0] = val + 2;
pr[i][j][mask][0] = 9;
}
int newmask = mask ^ (1 << i);
if(dp[i][j][newmask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 10)){
dp[i][j][newmask][1] = val + 2;
pr[i][j][newmask][1] = 10;
}
val = (i ? dp[i - 1][j][mask][1]: INF);
if(dp[i][j][newmask][0] > val + 1 && good(i * 2 + 1, j * 2 + 1, 11)){
dp[i][j][newmask][0] = val + 1;
pr[i][j][newmask][0] = 11;
}
}
else{
int val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 5)){
dp[i][j][mask][0] = val;
pr[i][j][mask][0] = 5;
}
int newmask = mask ^ (1 << i);
if(dp[i][j][newmask][1] > val + 3 && good(i * 2 + 1, j * 2 + 1, 6)){
dp[i][j][newmask][1] = val + 3;
pr[i][j][newmask][1] = 6;
}
val = (i ? dp[i - 1][j][mask][1]: INF);
if(dp[i][j][mask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 7)){
dp[i][j][mask][1] = val + 2;
pr[i][j][mask][1] = 7;
}
if(dp[i][j][newmask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 8)){
dp[i][j][newmask][0] = val + 2;
pr[i][j][newmask][0] = 8;
}
}
}
}
}
}
printf("%d", dp[n - 1][m - 1][0][0] + cntX / 2);
}
Compilation message
connect.cpp: In function 'void inputs()':
connect.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
17 | scanf("%d %d\n", &r, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
connect.cpp:19:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
19 | getline(cin, s[i]), scanf("\n");
| ~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
620 KB |
Partially correct (80% score). Wrong board |
| 2 |
Partially correct |
1 ms |
620 KB |
Partially correct (80% score). Wrong board |
| 3 |
Partially correct |
1 ms |
876 KB |
Partially correct (80% score). Wrong board |
| 4 |
Incorrect |
2 ms |
1536 KB |
Wrong score! (21, expected 28) |
| 5 |
Partially correct |
10 ms |
8300 KB |
Partially correct (80% score). Wrong board |
| 6 |
Partially correct |
3 ms |
1900 KB |
Partially correct (80% score). Wrong board |
| 7 |
Incorrect |
2 ms |
1260 KB |
Wrong score! (69, expected 72) |
| 8 |
Partially correct |
2 ms |
1772 KB |
Partially correct (80% score). Wrong board |
| 9 |
Partially correct |
3 ms |
2156 KB |
Partially correct (80% score). Wrong board |
| 10 |
Partially correct |
3 ms |
2796 KB |
Partially correct (80% score). Wrong board |
| 11 |
Partially correct |
3 ms |
2924 KB |
Partially correct (80% score). Wrong board |
| 12 |
Partially correct |
6 ms |
5228 KB |
Partially correct (80% score). Wrong board |
| 13 |
Incorrect |
7 ms |
5612 KB |
Wrong score! (197, expected 208) |
| 14 |
Partially correct |
7 ms |
7276 KB |
Partially correct (80% score). Wrong board |
| 15 |
Partially correct |
9 ms |
8684 KB |
Partially correct (80% score). Wrong board |
| 16 |
Partially correct |
11 ms |
9580 KB |
Partially correct (80% score). Wrong board |
| 17 |
Partially correct |
12 ms |
10604 KB |
Partially correct (80% score). Wrong board |
| 18 |
Partially correct |
23 ms |
20204 KB |
Partially correct (80% score). Wrong board |
| 19 |
Partially correct |
39 ms |
28652 KB |
Partially correct (80% score). Wrong board |
| 20 |
Incorrect |
27 ms |
24044 KB |
Wrong score! (368, expected 374) |
