TopCoder SRM 156 DIV 1 Hard 練習

やたーHard解けたよー

問題

壁のある場所にAとBの二人が居て、1ターンで二人が同時に一歩歩ける。AとBがそれぞれの位置を交換するには最短で何ターンかかるか。

解

幅を優先しちゃいます＾＾

ってわけで幅優先探索すれば終わり。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;

public class PathFinding {
    int[, , ,] p = new int[20, 20, 20, 20];
    bool[,] fld = new bool[20, 20];
    int fldx, fldy;
    int[] dx = { 1, 1, 1, 0, -1, -1, -1, 0, 0 };
    int[] dy = { -1, 0, 1, 1, 1, 0, -1, -1, 0 };
    public int minTurns(string[] board) {
        int Ax = 0, Bx = 0, Ay = 0, By = 0;

        fldx = board[0].Length;
        fldy = board.Length;
        for (int y = 0; y < board.Length; ++y)
            for (int x = 0; x < board[y].Length; ++x)
                if (board[y][x] == 'A')
                {
                    Ax = x; Ay = y;
                    fld[y, x] = true;
                }
                else if (board[y][x] == 'B')
                {
                    Bx = x; By = y;
                    fld[y, x] = true;
                }
                else if (board[y][x] == '.')
                    fld[y, x] = true;
                else
                    fld[y, x] = false;

        for (int i = 0; i < 20; ++i)
            for (int j = 0; j < 20; ++j)
                for (int k = 0; k < 20; ++k)
                    for (int l = 0; l < 20; ++l)
                        p[i, j, k, l] = -1;

        int ax = Ax, ay = Ay, bx = Bx, by = By;
        Queue<KeyValuePair<Point, Point>> Q = new Queue<KeyValuePair<Point, Point>>();
        Q.Enqueue(new KeyValuePair<Point, Point>(new Point(ax, ay), new Point(bx, by)));
        while (Q.Count > 0)
        { 
            KeyValuePair<Point, Point> v = Q.Dequeue();
            Point a = v.Key, b = v.Value;

            if (a.X == Bx && a.Y == By && b.X == Ax && b.Y == Ay) return p[a.X, a.Y, b.X, b.Y] + 1;

            for(int i = 0; i < 9; ++i)
                for(int j = 0; j < 9; ++j)
                    if (valid(a, b, i, j))
                    {
                        KeyValuePair<Point,Point> q = new KeyValuePair<Point, Point>(new Point(a.X + dx[i], a.Y + dy[i]), new Point(b.X + dx[j], b.Y + dy[j]));
                        if (p[q.Key.X, q.Key.Y, q.Value.X, q.Value.Y] != -1) continue;
                        p[q.Key.X, q.Key.Y, q.Value.X, q.Value.Y] = p[a.X, a.Y, b.X, b.Y] + 1;
                        Q.Enqueue(q);
                    }
        }
        return -1;
    }

    private bool valid(Point a, Point b, int i, int j)
    {
        Point na = new Point(a.X + dx[i], a.Y + dy[i]);
        Point nb = new Point(b.X + dx[j], b.Y + dy[j]);

        if (na.X < 0 || nb.X < 0 || na.Y < 0 || nb.Y < 0 || na.X >= fldx || nb.X >= fldx || na.Y >= fldy || nb.Y >= fldy || !fld[na.Y, na.X] || !fld[nb.Y, nb.X])
            return false;
        if (na.X == nb.X && na.Y == nb.Y)
            return false;
        if (na.X == b.X && na.Y == b.Y && nb.X == a.X && nb.Y == a.Y)
            return false;
        return true;
    }
}