| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #105789 | #247. 【Rujia Liu's Present 7】Mysterious Space Station | std | 100 | 27ms | 1072kb | C++ 03 | 8.5kb | 2016-11-02 21:57:08 | 2016-11-29 01:24:16 |
测评历史
你现在查看的是最新测评结果
- [2022-09-21 04:20:00]
- 系统更新:更新测评系统;移除 Java 7 和 Java 14;新增 Java 17;原 Java 7、Java 14 分别改用 Java 8、Java 17 测评
- (https://vfleaking.blog.uoj.ac/blog/5450)
- [2022-04-08 09:00:00]
- 系统更新:优化通信题的测试效率
- (https://vfleaking.blog.uoj.ac/blog/5450)
- [2021-12-30 04:12:55]
- 系统更新:更新 Linux 内核
- (https://vfleaking.blog.uoj.ac/blog/5450)
- [2021-07-05 01:10:00]
- 系统更新:更新编译器版本
- (https://vfleaking.blog.uoj.ac/blog/6666)
- [2021-04-02 00:03:30]
- 系统更新:更新测评机操作系统和编译器版本
- (https://vfleaking.blog.uoj.ac/blog/6666)
- [2021-02-19 19:52:00]
- 系统更新:UOJ开始保存测评记录历史
- (https://vfleaking.blog.uoj.ac/blog/6617)
- [2016-11-02 21:57:08]
- 提交
answer
// Modified by Rujia Liu from station2.cpp
#include <cstdio>
#include <cstring>
using namespace std;
#define Wall 0
#define Unknown 1
#define Nothing 2
#define Gate 3
#define MatchGate 4
int dire[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},{1,1},{1,-1},{-1,-1}};
char direchar[5] = "ESWN";
int n, m, gatenum;
int data[20][20]; /* the status of the fields */
int op[20][20];
int Round[20][20][400];
int Info[20][20][400];
int nowx, nowy; /* (nowx, nowy) is the present position of the robot */
struct Tfa {
int x, y, d, leng;
} fa[20][20], bakfa[20][20];
struct Tqueue {
int x, y;
} queue[400];
int way[400];
int backway[400];
int MoveRobot(char Direction)
{
printf("MoveRobot %c\n", Direction);
fflush(stdout);
int ret;
scanf("%d", &ret);
return ret;
}
void Answer(int pos1, int pos2)
{
printf("Answer %d %d\n", pos1, pos2);
fflush(stdout);
}
bool Readin()
{
int i, j;
char ch, row[20];
if(scanf("%d %d %d", &n, &m, &gatenum) != 3) return false;
if(!n) return false;
for (i = 0; i < n; i++) {
scanf("%s", row);
for (j = 0; j < m; j++)
{
ch = row[j];
if (ch == 'S') nowx = i, nowy = j;
if (ch == '*') data[i][j] = Wall;
else data[i][j] = Unknown;
}
}
return true;
}
void FillAround(int x, int y) /* since (x,y) is a Gate or a Wall, the fields */
/* around it should be Nothing */
{
int i, x1, y1;
for (i = 0; i < 8; i++)
{
x1 = x + dire[i][0];
y1 = y + dire[i][1];
if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < m && data[x1][y1] == Unknown)
data[x1][y1] = Nothing;
}
}
int NearWall(int x, int y)
{
int i, x1, y1;
if (data[x][y] != Nothing) return -1;
for (i = 0; i < 8; i++)
{
x1 = x + dire[i][0];
y1 = y + dire[i][1];
if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < m && data[x1][y1] == Wall)
return i;
}
return -1;
}
void GoRound(int sx, int sy, int dir)
{
int x, y, x1, y1, i, j, h, max;
int ok[20][20];
memset(ok, 0, sizeof(ok));
Round[sx][sy][0] = 0;
x = sx; y = sy;
while (1 == 1)
{
dir = (dir + 1) % 4;
x1 = x + dire[dir][0];
y1 = y + dire[dir][1];
if (data[x1][y1] == Wall)
{
if (ok[x1][y1] == 0)
{
Round[sx][sy][0]++;
Round[sx][sy][Round[sx][sy][0]] = dir;
Info[sx][sy][Round[sx][sy][0]] = 0;
ok[x1][y1] = 1;
}
} else
{
if (ok[x1][y1] == 0)
{
Round[sx][sy][0]++;
Round[sx][sy][Round[sx][sy][0]] = dir;
Info[sx][sy][Round[sx][sy][0]] = 1;
ok[x1][y1] = 1;
}
x = x1; y = y1;
dir = (dir + 2) % 4;
if (x == sx && y == sy) break;
}
}
max = 0;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if ((i != sx || j != sy) && NearWall(i,j) != -1)
{
x = i; y = j;
for (h = 1; h <= Round[sx][sy][0]; h++)
{
x1 = x + dire[Round[sx][sy][h]][0];
y1 = y + dire[Round[sx][sy][h]][1];
if (data[x1][y1] == Wall && Info[sx][sy][h] == 0)
continue;
if (data[x1][y1] == Nothing && Info[sx][sy][h] == 1)
{
x = x1; y = y1;
continue;
}
if (h > max) max = h;
break;
}
}
Round[sx][sy][0] = max;
}
void Initialize()
{
int i, j, h;
/*
memset(Round, 0, sizeof(Round));
memset(Info, 0, sizeof(Info));
memset(op, 0, sizeof(op));
memset(way, 0, sizeof(way));
memset(backway, 0, sizeof(backway));
memset(queue, 0, sizeof(queue));
*/
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (data[i][j] == Wall) FillAround(i,j);
h = 0;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (data[i][j] != Wall)
{
h++;
op[i][j] = h;
}
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (data[i][j] == Nothing)
{
h = NearWall(i,j);
if (h != -1)
{
if (h < 4)
GoRound(i,j,h);
else
GoRound(i,j,(h+3)%4);
}
}
}
void BFS(int nowx, int nowy)
{
int head, tail, x, y, x1, y1, i;
memset(fa, -1, sizeof(fa));
fa[nowx][nowy].d = 0; fa[nowx][nowy].leng = 0;
head = tail = 0; queue[head].x = nowx; queue[head].y = nowy;
while (head <= tail)
{
x = queue[head].x; y = queue[head].y;
for (i = 0; i < 4; i++)
{
x1 = x + dire[i][0];
y1 = y + dire[i][1];
if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < m &&
data[x1][y1] == Nothing && fa[x1][y1].d == -1)
{
tail++;
queue[tail].x = x1;
queue[tail].y = y1;
fa[x1][y1].x = x;
fa[x1][y1].y = y;
fa[x1][y1].d = i;
fa[x1][y1].leng = fa[x][y].leng + 1;
}
}
head++;
}
}
void MoveTo(int aimx, int aimy)
{
int x, y, x1, y1, i;
BFS(nowx, nowy);
x = aimx; y = aimy;
way[0] = fa[x][y].leng; i = way[0];
while (x != nowx || y != nowy)
{
way[i] = fa[x][y].d;
x1 = fa[x][y].x;
y1 = fa[x][y].y;
x = x1; y = y1; i--;
}
for (i = 1; i <= way[0]; i++)
MoveRobot(direchar[way[i]]);
nowx = aimx; nowy = aimy;
}
int Value(int x, int y)
{
int val;
val = 0;
val += bakfa[x][y].leng;
val += Round[x][y][0];
return -val;
}
void FindWayToWall()
{
int i, j, x, y, x1, y1;
BFS(nowx, nowy);
memcpy(bakfa, fa, sizeof(fa));
x = -1;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (NearWall(i,j) != -1 && bakfa[i][j].d != -1)
{
if (x == -1) x = i, y = j;
if (Value(i,j) > Value(x,y))
x = i, y = j;
}
way[0] = bakfa[x][y].leng; i = way[0];
while (x != nowx || y != nowy)
{
way[i] = bakfa[x][y].d;
x1 = bakfa[x][y].x;
y1 = bakfa[x][y].y;
x = x1; y = y1; i--;
}
}
void MoveBack()
{
int i;
for (i = backway[0]; i > 0; i--)
MoveRobot(direchar[(backway[i] + 2) % 4]);
}
int Test(int stdx, int stdy)
{
int i, j, sx, sy;
backway[0] = 0;
nowx = stdx; nowy = stdy;
FindWayToWall();
for (i = 1; i <= way[0]; i++)
{
j = MoveRobot(direchar[way[i]]);
if (j == 1)
{
backway[0]++;
backway[backway[0]] = way[i];
nowx = nowx + dire[way[i]][0];
nowy = nowy + dire[way[i]][1];
}
if (j == 0)
{
MoveBack();
return 0;
}
}
sx = nowx; sy = nowy;
for (i = 1; i <= Round[sx][sy][0]; i++)
{
j = MoveRobot(direchar[ Round[sx][sy][i] ]);
if (j == 1)
{
backway[0]++;
backway[backway[0]] = Round[sx][sy][i];
nowx = nowx + dire[Round[sx][sy][i]][0];
nowy = nowy + dire[Round[sx][sy][i]][1];
}
if (j != Info[sx][sy][i])
{
MoveBack();
return 0;
}
}
return 1;
}
void Judge()
{
int i, j, totgate;
totgate = 0;
for (i = n-1; i >= 0; i--)
for (j = m-1; j >= 0; j--)
if (data[i][j] == Unknown)
{
if (totgate == gatenum*2)
{
data[i][j] = Nothing;
continue;
}
MoveTo(i,j+1);
MoveRobot('W'); MoveRobot('S');
if (Test(i+1,j) == 1)
{
/* (i,j) is Nothing */
data[i][j] = Nothing;
} else
{
/* (i,j) is a Gate */
totgate++;
data[i][j] = Gate;
FillAround(i,j);
MoveRobot('N'); MoveRobot('E');
nowx = i; nowy = j+1;
}
}
}
void Match()
{
int i, j, i1, j1, i2, j2, totmatch;
totmatch = 0;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (data[i][j] == Gate)
{
if (totmatch + 1 == gatenum)
{
for (i1 = 0; i1 < n; i1++)
for (j1 = 0; j1 < m; j1++)
if (data[i1][j1] == Gate && (i1 != i || j1 != j)) {
Answer(op[i][j], op[i1][j1]);
return; // don't continue MoveRobot after answering everything!
}
}
MoveTo(i-1,j);
MoveRobot('S');
i2 = -1;
for (i1 = 0; i1 < n; i1++)
for (j1 = 0; j1 < m; j1++)
if (i2 == -1 && data[i1][j1] == Gate && (i1 != i || j1 != j))
{
if (Test(i1+1,j1) == 1)
{
i2 = i1;
j2 = j1;
}
}
Answer(op[i][j], op[i2][j2]);
data[i][j] = MatchGate;
data[i2][j2] = MatchGate;
totmatch++;
}
}
int main()
{
Readin();
Initialize();
Judge();
Match();
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 636kb
input:
7 8 1 ******** *****..* ***....* *.....** *S.....* *......* ******** 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1...
output:
MoveRobot S MoveRobot E MoveRobot E MoveRobot E MoveRobot E MoveRobot N MoveRobot W MoveRobot S Move...
result:
ok 51 commands
Test #2:
score: 10
Accepted
time: 1ms
memory: 696kb
input:
9 15 1 *************** *S..*********** *...*********** *...*********** *...*********** *...........*...
output:
MoveRobot E MoveRobot E MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot E MoveRobot E Move...
result:
ok 107 commands
Test #3:
score: 10
Accepted
time: 1ms
memory: 752kb
input:
11 11 2 *********** *....S***** *.....*...* **........* **........* *........** *........** ***........
output:
MoveRobot S MoveRobot S MoveRobot E MoveRobot E MoveRobot N MoveRobot E MoveRobot E MoveRobot S Move...
result:
ok 235 commands
Test #4:
score: 10
Accepted
time: 2ms
memory: 968kb
input:
15 15 2 *************** *S.*********..* *...*******...* ***..*****..*** *.....***.....* *......*.......
output:
MoveRobot E MoveRobot S MoveRobot E MoveRobot S MoveRobot E MoveRobot S MoveRobot E MoveRobot S Move...
result:
ok 220 commands
Test #5:
score: 10
Accepted
time: 2ms
memory: 832kb
input:
10 15 3 *************** *S............* *.............* *.............* *...******....* *...*....***...
output:
MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot E Move...
result:
ok 299 commands
Test #6:
score: 10
Accepted
time: 4ms
memory: 1072kb
input:
15 15 3 *************** *S..****......* *.....*.......* *.....*.....*** *.............* ********.......
output:
MoveRobot E MoveRobot E MoveRobot S MoveRobot E MoveRobot E MoveRobot S MoveRobot S MoveRobot E Move...
result:
ok 520 commands
Test #7:
score: 10
Accepted
time: 5ms
memory: 960kb
input:
15 15 4 *************** *...*...*.....* *.............* *.............* *********.....* **.............
output:
MoveRobot E MoveRobot E MoveRobot N MoveRobot N MoveRobot E MoveRobot E MoveRobot S MoveRobot S Move...
result:
ok 834 commands
Test #8:
score: 10
Accepted
time: 8ms
memory: 856kb
input:
15 15 4 *************** *S...********** *....********** *.............* *.............* *..............
output:
MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S Move...
result:
ok 1381 commands
Test #9:
score: 10
Accepted
time: 2ms
memory: 892kb
input:
15 15 5 *************** *S..*******...* *.....***.....* *......*......* *.............* *..............
output:
MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S Move...
result:
ok 379 commands
Test #10:
score: 10
Accepted
time: 2ms
memory: 880kb
input:
15 15 5 *************** *.......*..*.S* *.............* *............** *.............* *..............
output:
MoveRobot S MoveRobot W MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot S MoveRobot E Move...
result:
ok 408 commands

鄂公网安备 42010202000505 号