2010年01月の日記。

2010年01月07日

ソニーがSDカードに参入

ソニー純正のMicroSD/メモリスティックアダプタが販売されないでしょうか。

2010年01月12日

日本航空、法的整理へ

新規採用とか取ってたんですかね?

経路探索

入社試験の記事を教えていただいたのでとりあえず書いてみました。

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

#define WIN32_LEAN_AND_MEAN
#include <windows.h>

#define ARRAY(A,X,Y) ((A)[((Y)*map.x)+(X)])

struct size {
  int x;
  int y;
};

static char *maze;
static int *cost;
struct size map;
struct size goal;

HANDLE file;
HANDLE map_obj;

int load(char *);
int init(void);
int search(void);
int show(void);
int release(void);

int main(int argc, char **argv)
{
  if (load(argv[1])) {
    return 1;
  }

  init();
  search();
  show();

  release();

  return 0;
}

int load(char *mapdata)
{
  char *p;
  int x;
  int filesize;

  file = CreateFile(mapdata, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
  if (file == INVALID_HANDLE_VALUE) {
    return 1;
  }

  filesize = GetFileSize(file, NULL);

  map_obj = CreateFileMapping(file, NULL, PAGE_READONLY, 0, 0, NULL);
  if (!map_obj) {
    return 1;
  }

  maze = MapViewOfFile(map_obj, FILE_MAP_READ, 0, 0, 0);
  if (!maze) {
    return 1;
  }

  p = maze;

  x = 0;
  while (*p != '\n') {
    p++;
    x++;
  }

  map.x = x + 1;
  map.y = (filesize + (map.x - 1)) / map.x;

  cost = malloc(map.x * map.y * sizeof (int));
  memset(cost, 0, map.x * map.y * sizeof (int));

  return 0;
}

int init(void)
{
  int x;
  int y;

  memset(cost, 0, sizeof(cost));

  for (y = 0; y < map.y; y++) {
    for (x = 0; x < map.x; x++) {
      if (ARRAY(maze, x, y) == 'S') {
        ARRAY(cost, x, y) = 1;
      }

      if (ARRAY(maze, x, y) == 'G') {
        goal.y = y;
        goal.x = x;
      }
    }
  }

  return 0;
}

int search(void)
{
  int chk = 1;
  int x;
  int y;
  int vx;
  int vy;
  int xx;
  int yy;
  int loop = 1;

  while (loop) {
    loop = 0;
    for (y = 0; y < map.y; y++) {
      for (x = 0; x < map.x; x++) {
        if (ARRAY(cost, x, y) != chk) {
          continue;
        }

        for (vy = -1; vy < 2; vy++) {
          xx = x;
          yy = y + vy;
          if (0 < xx && 0 < yy && xx < map.x && yy < map.y) {
            if (ARRAY(maze, xx, yy) != '*' && ARRAY(cost, xx, yy) == 0) {
              ARRAY(cost, xx, yy) = chk + 1;
              loop = 1;
            }
          }
        }

        for (vx = -1; vx < 2; vx++) {
          xx = x + vx;
          yy = y;
          if (0 < xx && 0 < yy && xx < map.x && yy < map.y) {
            if (ARRAY(maze, xx, yy) != '*' && ARRAY(cost, xx, yy) == 0) {
              ARRAY(cost, xx, yy) = chk + 1;
              loop = 1;
            }
          }
        }

      }
    }
    ++chk;
  }

  return 0;
}

int show(void)
{
  int x;
  int y;
  int vx;
  int vy;
  int xx;
  int yy;
  int step;

  x = goal.x;
  y = goal.y;
  step = ARRAY(cost, x, y) - 1;

  while (step) {

    for (vy = -1; vy < 2; vy++) {
      xx = x;
      yy = y + vy;
      if (0 < xx && 0 < yy && xx < map.x && yy < map.y) {
        if (ARRAY(cost, xx, yy) == step) {
          ARRAY(cost, xx, yy) = 0;
          x = xx;
          y = yy;
          goto next;
        }
      }
    }

    for (vx = -1; vx < 2; vx++) {
      xx = x + vx;
      yy = y;
      if (0 < xx && 0 < yy && xx < map.x && yy < map.y) {
        if (ARRAY(cost, xx, yy) == step) {
          ARRAY(cost, xx, yy) = 0;
          x = xx;
          y = yy;
          goto next;
        }
      }
    }
  next:
    --step;
  }

  for (y = 0; y < map.y; y++) {
    for (x = 0; x < map.x; x++) {
      switch (ARRAY(maze, x, y)) {
      case ' ':
        if (ARRAY(cost, x, y) == 0) {
          printf("$");
        }else{
          printf(" ");
        }
        break;
      case '\r':
      case '\n':
        break;
      default:
        printf("%c", ARRAY(maze, x, y));
      }
    }
    printf("\n");
  }


  return 0;
}

int release(void)
{
  UnmapViewOfFile(maze);
  CloseHandle(map_obj);
  CloseHandle(file);
  free(cost);

  return 0;
}

迷路データを

という形で動かす分には20分程度で済んだのですが、「入出力にテキストデータを用いる」ということでマップドファイルを使おうとしたところload()の実装に30分くらいかかりました。