UOJ Logo Universal Online Judge

UOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105789#247. 【Rujia Liu's Present 7】Mysterious Space Stationstd10027ms1072kbC++ 038.5kb2016-11-02 21:57:082016-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)
  • [2016-11-29 01:24:16]
  • 评测
  • 测评结果:100
  • 用时:27ms
  • 内存:1072kb
  • [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