// 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 100000
enum AddType
{
addEnd = 0,
addDown = 1,
addRight = 2,
addDownAndRight
};
class Record
{
public:
unsigned int state;
unsigned short score;
unsigned int record[40];
unsigned char x, y;
Record() {}
};
char cells[MAX_H][MAX_W];
Record qs[QS_SIZE];
int qHead, qTail;
#define IS_EMPTY (qHead == qTail)
#define IS_FULL (qHead == ((qTail + 1) % QS_SIZE))
int h, w;
unordered_map<unsigned int, unsigned int> cnts;
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, X, Y) \
unordered_map<unsigned int, unsigned int>::iterator it = cnts.find(ST); \
if (it != cnts.end() && ST == qs[it->second].state && X == qs[it->second].x && Y == qs[it->second].y) \
{ \
int pInQ = it->second; \
if (qs[pInQ].score > SCORE) \
{ \
qs[pInQ].score = SCORE; \
memcpy(qs[pInQ].record, REC, sizeof(REC)); \
qs[pInQ].record[now_x >> 1] &= ~(3 << now_y); \
qs[pInQ].record[now_x >> 1] |= TYPE << now_y; \
} \
} \
else \
{ \
int pInQ = qTail; \
qs[pInQ].state = ST; \
qs[pInQ].score = SCORE; \
qs[pInQ].x = X; \
qs[pInQ].y = Y; \
memcpy(qs[pInQ].record, REC, sizeof(REC)); \
qs[pInQ].record[now_x >> 1] &= ~(3 << now_y); \
qs[pInQ].record[now_x >> 1] |= TYPE << now_y; \
cnts[ST] = pInQ; \
qTail = (qTail + 1) % QS_SIZE; \
}
#define forwardFunc(newSt, plusVal, minusVal, newVal) \
{ \
int pos = (now_y >> 1) + 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 >> 1) - 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
now_x = 0;
now_y = w - 1;
qs[qTail].state = 0;
qs[qTail].score = 0;
qs[qTail].x = now_x;
qs[qTail].y = now_y;
qTail++;
while (false == IS_EMPTY)
{
unsigned int st = qs[qHead].state;
unsigned short score = qs[qHead].score;
now_x = qs[qHead].x;
now_y = qs[qHead].y;
if ((w - 1) == now_y)
{
now_x += 2;
now_y = 2;
if (h < now_x)
{
if (0 == qs[qHead].state)
{
cout << qs[qHead].score << endl;
for (size_t row = 1; row <= (h >> 1); row++)
{
for (size_t col = 1; col <= (w >> 1); col++)
{
int tmp = (qs[qHead].record[row] >> (2 * col)) & 3;
if (addEnd == tmp)
{
if ('X' != cells[row << 1][col << 1])
{
if ('.' == cells[(row << 1) - 1][col << 1] || '.' == cells[row << 1][(col << 1) - 1])
{
cells[row << 1][col << 1] = '.';
}
}
}
else if (addDown == tmp)
{
if ('X' != cells[row << 1][col << 1])
{
cells[row << 1][col << 1] = '.';
}
cells[(row << 1) + 1][col << 1] = '.';
}
else if (addRight == tmp)
{
if ('X' != cells[row << 1][col << 1])
{
cells[row << 1][col << 1] = '.';
}
cells[row << 1][(col << 1) + 1] = '.';
}
else
{
cells[row << 1][col << 1] = '.';
cells[(row << 1) + 1][col << 1] = '.';
cells[row << 1][(col << 1) + 1] = '.';
}
}
}
if (bSwitch)
{
for (size_t col = 1; col <= w; col++)
{
for (size_t row = 1; row <= h; row++)
{
cout << cells[row][col];
}
cout << endl;
}
}
else
{
for (size_t row = 1; row <= h; row++)
{
for (size_t col = 1; col <= w; col++)
{
cout << cells[row][col];
}
cout << endl;
}
}
}
break;
}
}
else
{
now_y += 2;
}
if (2 == now_y)
{
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
qHead = (qHead + 1) % QS_SIZE;
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
qHead = (qHead + 1) % QS_SIZE;
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[qHead].record, now_x, now_y);
}
}
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[qHead].record, now_x, now_y);
}
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[qHead].record, now_x, now_y);
}
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[qHead].record, now_x, now_y);
}
}
}
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[qHead].record, now_x, now_y);
}
if (' ' == cells[now_x][now_y + 1])
{
unsigned int newSt = st;
setVal4St(newSt, (now_y >> 1), 3);
addSts(newSt, addRight, (score + 1), qs[qHead].record, now_x, now_y);
}
}
else
{
unsigned int newSt = st;
// do nonthing
addSts(newSt, addEnd, score, qs[qHead].record, now_x, now_y);
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[qHead].record, now_x, now_y);
}
}
}
qHead = (qHead + 1) % QS_SIZE;
}
return 0;
}
Compilation message
connect.cpp: In function 'int main()':
connect.cpp:202:46: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
202 | for (size_t row = 1; row <= (h >> 1); row++)
| ~~~~^~~~~~~~~~~
connect.cpp:204:50: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
204 | for (size_t col = 1; col <= (w >> 1); col++)
| ~~~~^~~~~~~~~~~
connect.cpp:244:50: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
244 | for (size_t col = 1; col <= w; col++)
| ~~~~^~~~
connect.cpp:246:54: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
246 | for (size_t row = 1; row <= h; row++)
| ~~~~^~~~
connect.cpp:255:50: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
255 | for (size_t row = 1; row <= h; row++)
| ~~~~^~~~
connect.cpp:257:54: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
257 | for (size_t col = 1; col <= w; col++)
| ~~~~^~~~
connect.cpp:143:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | scanf("%d %d\n", &h, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
40 ms |
20332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 10 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
5 ms |
9052 KB |
Output is correct |
| 12 |
Correct |
5 ms |
10844 KB |
Output is correct |
| 13 |
Correct |
6 ms |
11100 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 17 |
Correct |
5 ms |
7260 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 19 |
Execution timed out |
978 ms |
42936 KB |
Time limit exceeded |
| 20 |
Correct |
18 ms |
18360 KB |
Output is correct |
