2012年8月18日

UVa 101 - The Blocks Problem


#include <stdio.h>
#include <string.h>

typedef struct {
  int loc;
  int num;
} Block;
Block block[25];
int map[25][25];

void put (int a, int b) {
  int i, j, loc = block[a].loc, nloc = block[b].loc;
  for (i = 0; map[nloc][i] != -1; i++);
  for (j = 0; map[loc][j] != a; j++);
  map[nloc][i] = map[loc][j];
  map[loc][j] = -1;
  block[a].loc = nloc;
}

void pile (int a, int b) {
  int i, j, loc = block[a].loc, nloc = block[b].loc;
  for (i = 0; map[nloc][i] != -1; i++);
  for (j = 0; map[loc][j] != a; j++);
  for ( ; map[loc][j] != -1; j++) {
    block[map[loc][j]].loc = nloc;
    map[nloc][i++] = map[loc][j];
    map[loc][j] = -1;
  }
}

void returning (int n) {
  int i, j, loc = block[n].loc, nloc;
  for (i = 0; map[loc][i] != n; i++);
  for (i++; map[loc][i] != -1; i++) {
    nloc = block[map[loc][i]].num;
    for (j = 0; map[nloc][j] != -1; j++);
    map[nloc][j] = map[loc][i];
    block[map[loc][i]].loc = nloc;
    map[loc][i] = -1;
  }
}

int main() {
  int i, j, n;
  while (scanf("%d", &n) == 1) {
    getchar();
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++)
        map[i][j] = -1;
      block[i].loc = i;
      block[i].num = i;
      map[i][0] = i;
    }

    char action[10], method[10];
    int a, b;
    while (scanf("%s", &action)) {
      if (action[0] == 'q')
        break;
      scanf(" %d %s %d", &a, &method, &b);
      if (block[a].loc == block[b].loc)
        continue;
      if (!strcmp(action, "move")) {
        returning(a);
        if (!strcmp(method, "onto"))
          returning(b);
        put(a, b);
      } else {
        if (!strcmp(method, "onto"))
          returning(b);
        pile(a, b);
      }
    }
    for (i = 0; i < n; i++) {
      printf("%d:", i);
      for (j = 0; map[i][j] != -1; j++)
        printf(" %d", map[i][j]);
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言