// https://oj.uz/problem/view/CEOI06_connect
#include <cmath>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <queue>
#include <stack>
#include <climits>
#include <cfloat>
#include <limits>
#include <bitset>
#include <cstring>
using namespace std;
#define MAX_H 80
#define MAX_W 26
#define ST_BITS 2
#define ST_MASK 3
#define QS_SIZE 500000
enum AddType
{
addSkip,
addEnd,
addDown,
addRight,
addDownAndRight
};
class Record
{
public:
unsigned int state;
unsigned int score;
char record[MAX_H][MAX_W];
Record() {}
};
char cells[MAX_H][MAX_W];
Record qs[2][QS_SIZE];
int qTail[2];
int h, w;
unordered_map<unsigned int, unsigned int> cnts[2];
int act = 0; // 当前生效的 map
int now_x, now_y;
#define getVal4St(ST, POS) ((ST) >> ((POS) * ST_BITS)) & ST_MASK
#define setVal4St(ST, POS, VAL) \
ST &= ~(ST_MASK << ((POS) * ST_BITS)); \
if (VAL) \
ST |= (VAL) << ((POS) * ST_BITS);
#define addSts(ST, TYPE, SCORE, REC, IDX) \
unordered_map<unsigned int, unsigned int>::iterator it = cnts[IDX].find(ST); \
if (it == cnts[IDX].end()) \
{ \
int pInQ = qTail[IDX]; \
qs[IDX][pInQ].state = ST; \
qs[IDX][pInQ].score = SCORE; \
memcpy(qs[IDX][pInQ].record, REC, sizeof(REC)); \
if (addSkip != TYPE) \
{ \
if ('X' != qs[IDX][pInQ].record[now_x][now_y]) \
qs[IDX][pInQ].record[now_x][now_y] = '.'; \
if (TYPE == addDown) \
{ \
qs[IDX][pInQ].record[now_x + 1][now_y] = '.'; \
} \
else if (TYPE == addRight) \
{ \
qs[IDX][pInQ].record[now_x][now_y + 1] = '.'; \
} \
else if (TYPE == addDownAndRight) \
{ \
qs[IDX][pInQ].record[now_x + 1][now_y] = '.'; \
qs[IDX][pInQ].record[now_x][now_y + 1] = '.'; \
} \
} \
cnts[IDX][ST] = pInQ; \
qTail[IDX]++; \
} \
else \
{ \
int pInQ = it->second; \
if (qs[IDX][pInQ].score > SCORE) \
{ \
qs[IDX][pInQ].score = SCORE; \
memcpy(qs[IDX][pInQ].record, REC, sizeof(REC)); \
if (addSkip != TYPE) \
{ \
if ('X' != qs[IDX][pInQ].record[now_x][now_y]) \
qs[IDX][pInQ].record[now_x][now_y] = '.'; \
if (TYPE == addDown) \
{ \
qs[IDX][pInQ].record[now_x + 1][now_y] = '.'; \
} \
else if (TYPE == addRight) \
{ \
qs[IDX][pInQ].record[now_x][now_y + 1] = '.'; \
} \
else if (TYPE == addDownAndRight) \
{ \
qs[IDX][pInQ].record[now_x + 1][now_y] = '.'; \
qs[IDX][pInQ].record[now_x][now_y + 1] = '.'; \
} \
} \
} \
}
#define forwardFunc(newSt, plusVal, minusVal, newVal) \
{ \
int pos = now_y + 1; \
int s = 1; \
while (pos <= (w >> 1)) \
{ \
int v = getVal4St(newSt, pos); \
if (plusVal == v) \
s++; \
else if (minusVal == v) \
{ \
s--; \
if (0 == s) \
{ \
setVal4St(newSt, pos, newVal); \
break; \
} \
} \
pos++; \
} \
}
#define backwardFunc(newSt, plusVal, minusVal, newVal) \
{ \
int pos = now_y - 2; \
int s = 1; \
while (0 <= pos) \
{ \
int v = getVal4St(newSt, pos); \
if (plusVal == v) \
s++; \
else if (minusVal == v) \
{ \
s--; \
if (0 == s) \
{ \
setVal4St(newSt, pos, newVal); \
break; \
} \
} \
pos--; \
} \
}
int main()
{
bool bSwitch = false;
scanf("%d %d\n", &h, &w);
if (h < w)
{
bSwitch = true;
}
for (int i = 1; i <= h; i++)
{
string s;
getline(cin, s);
for (int j = 1; j <= w; j++)
{
if (bSwitch)
{
cells[j][i] = s.at(j - 1);
}
else
{
cells[i][j] = s.at(j - 1);
}
}
}
if (bSwitch)
{
swap(h, w);
}
// init
act = 0;
now_x = 0;
now_y = w - 1;
qs[act][0].state = 0;
qs[act][0].score = 0;
memcpy(qs[act]->record, cells, sizeof(cells));
qTail[act]++;
while (0 < qTail[act])
{
int nAct = 1 - act;
if ((w - 1) == now_y)
{
now_x += 2;
now_y = 2;
if (h < now_x)
{
if (1 == qTail[act] && 0 == qs[act][0].state)
{
cout << qs[act][0].score << endl;
if (bSwitch)
{
for (size_t col = 1; col <= w; col++)
{
for (size_t row = 1; row <= h; row++)
{
cout << qs[act][0].record[row][col];
}
cout << endl;
}
}
else
{
for (size_t row = 1; row <= h; row++)
{
for (size_t col = 1; col <= w; col++)
{
cout << qs[act][0].record[row][col];
}
cout << endl;
}
}
}
break;
}
}
else
{
now_y += 2;
}
for (size_t iQ = 0; iQ < qTail[act]; iQ++)
{
unsigned int st = qs[act][iQ].state;
unsigned int score = qs[act][iQ].score;
if (1 == (now_y >> 1))
{
st <<= ST_BITS;
}
unsigned int left = getVal4St(st, (now_y >> 1) - 1);
unsigned int up = getVal4St(st, (now_y >> 1));
if (left && up)
{
if ('X' == cells[now_x][now_y])
{
// invalid
continue;
}
else
{
unsigned int newSt = st;
setVal4St(newSt, (now_y >> 1) - 1, 0);
setVal4St(newSt, (now_y >> 1), 0);
if (3 == left || 3 == up)
{
if (1 == left || 1 == up)
{
// 1, 3
forwardFunc(newSt, 1, 2, 3);
}
else if (2 == left || 2 == up)
{
// 2, 3
backwardFunc(newSt, 2, 1, 3);
}
else
{
// 3, 3
// do nothing
}
}
else if (1 == left && 1 == up)
{
forwardFunc(newSt, 1, 2, 1);
}
else if (1 == left && 2 == up)
{
// invalid
continue;
}
else if (2 == left && 1 == up)
{
// do nothin
}
else
{
// 2 == left && 2 == up
backwardFunc(newSt, 2, 1, 2);
}
addSts(newSt, addEnd, (score + 2), qs[act][iQ].record, nAct);
}
}
else if (left || up)
{
unsigned int val = left + up;
if ('X' == cells[now_x][now_y])
{
unsigned int newSt = st;
setVal4St(newSt, (now_y >> 1) - 1, 0);
setVal4St(newSt, (now_y >> 1), 0);
if (3 == val)
{
}
else if (1 == val)
{
forwardFunc(newSt, 1, 2, 3);
}
else
{
// 2 == val
backwardFunc(newSt, 2, 1, 3);
}
addSts(newSt, addEnd, (score + 1), qs[act][iQ].record, nAct);
}
else
{
if (' ' == cells[now_x + 1][now_y])
{
unsigned int newSt = st;
setVal4St(newSt, (now_y >> 1) - 1, val);
setVal4St(newSt, (now_y >> 1), 0);
addSts(newSt, addDown, (score + 2), qs[act][iQ].record, nAct);
}
if (' ' == cells[now_x][now_y + 1])
{
unsigned int newSt = st;
setVal4St(newSt, (now_y >> 1) - 1, 0);
setVal4St(newSt, (now_y >> 1), val);
addSts(newSt, addRight, (score + 2), qs[act][iQ].record, nAct);
}
}
}
else
{
// 0 == left && 0 == up
if ('X' == cells[now_x][now_y])
{
if (' ' == cells[now_x + 1][now_y])
{
unsigned int newSt = st;
setVal4St(newSt, (now_y >> 1) - 1, 3);
addSts(newSt, addDown, (score + 1), qs[act][iQ].record, nAct);
}
if (' ' == cells[now_x][now_y + 1])
{
unsigned int newSt = st;
setVal4St(newSt, (now_y >> 1), 3);
addSts(newSt, addRight, (score + 1), qs[act][iQ].record, nAct);
}
}
else
{
unsigned int newSt = st;
// do nonthing
addSts(newSt, addSkip, score, qs[act][iQ].record, nAct);
if (' ' == cells[now_x + 1][now_y] && ' ' == cells[now_x][now_y + 1])
{
setVal4St(newSt, (now_y >> 1) - 1, 1);
setVal4St(newSt, (now_y >> 1), 2);
addSts(newSt, addDownAndRight, (score + 2), qs[act][iQ].record, nAct);
}
}
}
}
qTail[act] = 0;
cnts[act].clear();
act = nAct;
}
return 0;
}
Compilation message
connect.cpp: In function 'int main()':
connect.cpp:228:50: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
228 | for (size_t col = 1; col <= w; col++)
| ~~~~^~~~
connect.cpp:230:54: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
230 | for (size_t row = 1; row <= h; row++)
| ~~~~^~~~
connect.cpp:239:50: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
239 | for (size_t row = 1; row <= h; row++)
| ~~~~^~~~
connect.cpp:241:54: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
241 | for (size_t col = 1; col <= w; col++)
| ~~~~^~~~
connect.cpp:257:32: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
257 | for (size_t iQ = 0; iQ < qTail[act]; iQ++)
| ~~~^~~~~~~~~~~~
connect.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
170 | scanf("%d %d\n", &h, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Runtime error |
57 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
12 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
5 ms |
6748 KB |
Output is correct |
| 9 |
Incorrect |
12 ms |
15196 KB |
Wrong score! (136, expected 132) |
| 10 |
Correct |
11 ms |
6748 KB |
Output is correct |
| 11 |
Runtime error |
39 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Correct |
14 ms |
7004 KB |
Output is correct |
| 13 |
Correct |
17 ms |
8792 KB |
Output is correct |
| 14 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
2396 KB |
Unexpected end of file - int32 expected |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
19 ms |
21500 KB |
Output is correct |
| 18 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 19 |
Runtime error |
34 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Correct |
49 ms |
31828 KB |
Output is correct |
