2013年2月28日

UVa 383 - Shipping Routes


#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int main() {
  int T, C = 1;
  scanf("%d", &T);
  puts("SHIPPING ROUTES OUTPUT");
  while (T--) {
    puts("");
    printf("DATA SET  %d\n", C++);
    puts("");
    int m, n, p;
    scanf("%d%d%d", &m, &n, &p);
    while (m--) {
      char s[20];
      scanf("%s", s);
    }
    map<string, vector<string> > con;
    while (n--) {
      char s1[20], s2[20];
      scanf("%s%s", s1, s2);
      con[string(s1)].push_back(string(s2));
      con[string(s2)].push_back(string(s1));
    }
    while (p--) {
      int size;
      char s1[20], s2[20];
      scanf("%d%s%s", &size, s1, s2);
      queue<string> q;
      map<string, int> dis;
      q.push(string(s1));
      dis[string(s1)] = 0;
      bool find = 0;
      while (!q.empty()) {
        string now = q.front();
        int d = dis[now];
        q.pop();
        if (now == string(s2)) {
          find = 1;
          printf("$%d\n", d * size * 100);
          break;
        }
        int i;
        for (i = 0; i < con[now].size(); i++)
          if (!dis.count(con[now][i])) {
            q.push(con[now][i]);
            dis[con[now][i]] = d + 1;
          }
      }
      if (!find) puts("NO SHIPMENT POSSIBLE");
    }
  }
  puts("\nEND OF OUTPUT");
  return 0;
}

UVa 10496 - Collecting Beepers


#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;
typedef set<P> S;
typedef pair<P, S> PP;
const int dr[] = {0, 1, 0, -1};
const int dc[] = {1, 0, -1, 0};

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int R, C, sr, sc, n;
    scanf("%d%d%d%d%d", &R, &C, &sr, &sc, &n);
    S s;
    while (n--) {
      int a, b;
      scanf("%d%d", &a, &b);
      s.insert(MP(a, b));
    }
    s.erase(MP(sr, sc));
    queue<PP> q;
    map<PP, int> dis;
    q.push(MP(MP(sr, sc), s));
    dis[MP(MP(sr, sc), s)] = 0;
    int min = 2e9;
    while (!q.empty()) {
      int r = q.front().first.first, c = q.front().first.second;
      s = q.front().second;
      int d = dis[q.front()];
      q.pop();
      if (!s.size()) {
        d = d + (int)abs(sr - r) + (int)abs(sc - c);
        min = d < min ? d : min;
        continue;
      }
      int i;
      for (i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (nr && nr <= R && nc && nc <= C) {
          PP next;
          if (s.count(MP(nr, nc))) {
            S ns = s;
            ns.erase(MP(nr, nc));
            next = MP(MP(nr, nc), ns);
          } else {
            next = MP(MP(nr, nc), s);
          }
          if (!dis.count(next)) {
            q.push(next);
            dis[next] = d + 1;
          }
        }
      }
    }
    printf("The shortest path has length %d\n", min);
  }
  return 0;
}

UVa 10363 - Tic Tac Toe


#include <cstdio>
#include <string>
#include <queue>
#include <set>
#define MP make_pair
using namespace std;

typedef pair<string, bool> P;

bool win(string s) {
  int r, c;
  for (r = 0; r < 3; r++)
    if (s[r * 3] != '.' && s[r * 3] == s[r * 3 + 1] && s[r * 3 + 1] == s[r * 3 + 2]) return 1;
  for (c = 0; c < 3; c++)
    if (s[c] != '.' && s[c] == s[c + 3] && s[c + 3] == s[c + 6]) return 1;
  if (s[0] != '.' && s[0] == s[4] && s[4] == s[8]) return 1;
  if (s[2] != '.' && s[2] == s[4] && s[4] == s[6]) return 1;
  return 0;
}

int main() {
  string s(".........");
  set<string> dic;
  queue<P> q;
  dic.insert(s);
  q.push(MP(s, 0));
  while (!q.empty()) {
    string now = q.front().first;
    bool turn = q.front().second;
    q.pop();
    if (win(now)) {
      dic.insert(now);
      continue;
    }
    int i;
    for (i = 0; i < 9; i++) {
      string next(now);
      if (next[i] == '.') {
        next[i] = turn ? 'O' : 'X';
        if (!dic.count(next)) {
          q.push(MP(next, !turn));
          dic.insert(next);
        }
      }
    }
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    char s1[10], s2[10], s3[10];
    scanf("%s%s%s", s1, s2, s3);
    puts(dic.count(string(s1) + s2 + s3) ? "yes" : "no");
  }
  return 0;
}

2013年2月24日

UVa 628 - Passwords


#include <stdio.h>

int n, m, len, con[25][25];

void run(int now, char* rule, char* s) {
  int i;
  if (!rule[now]) {
    for (i = 0; rule[i]; i++)
      if (rule[i] == '#') printf("%s", s);
      else putchar(rule[i]);
    puts("");
    return;
  }
  if (rule[now] == '0') {
    for (i = 0; i < 10; i++) {
      rule[now] = i + '0';
      run(now + 1, rule, s);
    }
    rule[now] = '0';
  } else {
    run(now + 1, rule, s);
  }
}

int main() {
  while (scanf("%d\n", &n) == 1) {
    int i;
    char s[101][101];
    for (i = 0; i < n; i++)
      gets(s[i]);
    scanf("%d\n", &m);
    puts("--");
    while (m--) {
      char rule[999];
      gets(rule);
      for (i = 0; i < n; i++)
        run(0, rule, s[i]);
    }
  }
  return 0;
}

UVa 539 - The Settlers of Catan


#include <stdio.h>

int n, m, len, con[25][25];

void find(int now, int l) {
  int i;
  if (l > len) len = l;
  for (i = 0; i < n; i++)
    if (con[now][i]) {
      con[now][i] = con[i][now] = 0;
      find(i, l + 1);
      con[now][i] = con[i][now] = 1;
    }
}

int main() {
  while (scanf("%d%d", &n, &m) && n || m) {
    int i, j;
    for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
        con[i][j] = 0;
    while (m--) {
      scanf("%d%d", &i, &j);
      con[i][j] = con[j][i] = 1;
    }
    len = 0;
    for (i = 0; i < n; i++)
      find(i, 0);
    printf("%d\n", len);
  }
  return 0;
}