AOJ 1166: 迷図と命ず / Amazing Mazes

問題

• https://onlinejudge.u-aizu.ac.jp/problems/1166

問題文

問題概要

迷路を表すデータが与えられる.

入口から出口までの最短経路の長さを求めよ.

制約

• 
• データセット数 :

解答例

指針

• BFS

解説

二次元グリッド上の最短経路問題なので幅優先探索(Breadth First Search: BFS)をすればいいのは, すぐに分かる.

しかし迷路の壁のデータが与えられるという少しトリッキーな形式なので注意が必要.

各座標の4方向に関して, 移動できるかどうかを値として保持するようにすればこの問題を解くことができる.

• C++ による実装例

// submission: https://onlinejudge.u-aizu.ac.jp/status/users/kira924age/submissions/1/1166/judge/4082763/C++

#include <iostream>
#include <queue>

using namespace std;

int h, w;
// maze[y][x][i] = 1 -> (x, y) は (dx[i], dy[i]) 方向に移動可能
int maze[100][100][4];
int dist[100][100];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, 1, -1, 0};

struct sets { int x, y, d; };

void init() {
  for (int i = 0; i < 100; i++) {
    for(int j = 0; j < 100; j++) {
      for (int k = 0; k < 4; k++) {
        maze[i][j][k] = 0;
      }
    }
  }
  for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
      dist[i][j] = -1;
    }
  }
}

int bfs() {
  queue<sets> q;
  q.push( sets{0, 0, 0} );
  dist[0][0] = 0;

  while (!q.empty()) {
    sets cur = q.front(); q.pop();
    int x = cur.x;
    int y = cur.y;
    int d = cur.d;
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];

      if ( maze[y][x][i] == 0 ) { continue; }
      if ( dist[ny][nx] != -1 ) { continue; }

      q.push( sets{nx, ny, d+1} );
      dist[ny][nx] = d+1;
    }
  }
  return dist[h-1][w-1] + 1;
}

int main() {
  while (cin >> w >> h) {
    if (h == 0 && w == 0) { break; }
    init();
    for (int i = 0; i < 2*h-1; i++) {
      if (i & 1) {
        for (int j = 0; j < w; j++) {
          int t; cin >> t;
          if (t == 0) {
            maze[i/2][j][1] = 1;
            maze[i/2+1][j][2] = 1;
          }
        }
      } else {
        for (int j = 0; j < w-1; j++) {
          int t; cin >> t;
          if (t == 0) {
            maze[i/2][j][3] = 1;
            maze[i/2][j+1][0] = 1;
          }
        }
      }
    }
    cout << bfs() << endl;
  }
  return 0;
}

• Python3 による実装例

# submission: https://onlinejudge.u-aizu.ac.jp/status/users/kira924age/submissions/1/1166/judge/4082821/Python3

import queue

def bfs(w, h, maze):
    dx = [-1, 0, 0, 1]
    dy = [0, 1, -1, 0]
    dist = [ [-1] * (w+1) for _ in range(h+1) ]
    q = queue.Queue()
    q.put([0, 0, 0])
    dist[0][0] = 0

    while not q.empty():
        x, y, d = q.get()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if maze[y][x][i] == 0: continue
            if dist[ny][nx] != -1: continue
            
            q.put( [nx, ny, d+1] )
            dist[ny][nx] = d+1

    return dist[h-1][w-1] + 1

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    maze = [ [[0] * 4 for x in range(w+1)] for _ in range(h+1) ]

    for i in range(h*2-1):
        if i & 1:
            t = [ int(x) for x in input().split() ]
            for j, tt in enumerate(t):
                if tt == 0:
                    maze[i//2][j][1] = 1
                    maze[i//2+1][j][2] = 1
        else:
            t = [ int(x) for x in input().split() ]
            for j, tt in enumerate(t):
                if tt == 0:
                    maze[i//2][j][3] = 1
                    maze[i//2][j+1][0] = 1
    print(bfs(w, h, maze))