2013年8月15日

UVa 10285 - Longest Run on a Snowboard

#include <cstdio>
#include <cstring>

const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};
int R, C, h[100][100], rec[100][100], max;

void run(int r, int c, int len) {
  max = len > max ? len : max;
  for (int i = 0; i < 4; i++) {
    int nr = r + dr[i], nc = c + dc[i];
    if (nr < 0 || nr >= R || nc < 0 || nc >= C || h[nr][nc] >= h[r][c] || rec[nr][nc] >= len + 1) {
      continue;
    }
    rec[nr][nc] = len + 1;
    run(nr, nc, len + 1);
  }
}

int main() {
  int N;
  scanf("%d", &N);
  while (N--) {
    char name[99];
    scanf("%s%d%d", name, &R, &C);
    for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
        scanf("%d", &h[r][c]);
      }
    }
    int ans = 0;
    for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
        max = 0;
        memset(rec, 0, sizeof(rec));
        run(r, c, 0);
        ans = max > ans ? max : ans;
      }
    }
    printf("%s: %d\n", name, ans + 1);
  }
  return 0;
}

沒有留言:

張貼留言