UVa 10952. Pattern Transformations

Description

Consider the two patterns of ‘O’ and ‘X’ below (‘.’ represent an empty square). We want the first pattern to be transformed into the second pattern in one time unit. During this time unit, each symbol (‘O’ and ‘X’) can move one step in any of the four directions (or remain at its current square). All movements happen simultaneously, so a symbol can move to an occupied square, if that symbol is moved to some other square. If a symbol moves from square A to B, and the symbol at B moves to A, we have a swap. Write a program which calculates the least number of swaps needed to transform a given pattern into another given pattern.

.XO..  ..XO.  
..OX.  .XX..  
.XX..  ..OX.  

To transform the first pattern above into the second one requires one swap: The two symbols in the first line are moved to the right, the ‘O’ in the second line must be swapped with the ‘X’ below. The other two ‘X’ are moved up and down, respectively.

Input Format

The first line in the input contains the number of test cases to follow (at most 20). Each test case starts with a line containing two integers, w and h ($1 \le w, h \le 8$), the width and height of the two patterns. Then follow h lines describing each row of the two patterns (the two patterns will be separated with a single space, see the sample input). The only allowed characters in the patterns will be the symbols ‘O’, ‘X’ and ‘.’.

Output Format

For each input you should output a line containing a single integer: the least number of swaps required to transform the first pattern into the second. If the transformation is not possible, output a ‘-1’.

Sample Input

3  
5 3  
.XO.. ..XO.  
..OX. .XX..  
.XX.. ..OX.  
4 4  
OXOX XOXO  
XX.O OX.X  
O..X X..O  
XOXO OXOX  
3 4  
.X. .X.  
.OX XO.  
..O .O.  
... ...

Sample Output

0  
0  
-1  

UVa - 10952

Solution

這題令我印象最深刻的就是我是這題的Topcoder：AC 0.000sec。
這題主要是考驗如何以bit來表示狀態，以及在寫狀態轉移式時的細心程度，再利用DFS來達成搜尋目的。
在我的程式裡面，共有四個狀態，分別是當前垂直、水平改變，以及上一行的垂直、水平改變。
以水平為例，第i位的0代表未有O或X移動到第i位置，若是1則相反。若是垂直的狀態，1則代表有往下移動。
若只以上述的想法來寫，會TLE，所以需要以DP的方式將重複狀態的DFS記錄下來（下面程式的38~41行）。
注意！此題第一測資答案為0，在上方題目範例已修正

Code

/*************************************************************************
  > File Name: 10952 - Pattern Transformations.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Sat Jul 28 11:22:06 2018
*************************************************************************/

#include <bits/stdc++.h>
using namespace std;

const int inf = 1 << 30;
int n, m, c;
char s[8][8], e[8][8];
int dp[8][1 << 8][1 << 8], run[8][1 << 8][1 << 8];
int dfs(int, int, int, int, int, int);
int sol(int, int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> c;
    while (c--) {
        cin >> m >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                cin >> s[i][j];
            for (int j = 0; j < m; j++)
                cin >> e[i][j];
        }
        int ans = sol(0, 0, (1 << m) - 1);
        cout << (ans == inf ? -1 : ans) << '\n';
    }
    return 0;
}
int sol(int row, int prev_ver, int prev_hor) { //垂直 平行
    if (row == n)
        return (!prev_ver && prev_hor == (1 << m) - 1) ? 0 : inf;
    if (run[row][prev_ver][prev_hor] == c)
        return dp[row][prev_ver][prev_hor];
    run[row][prev_ver][prev_hor] = c;
    return dp[row][prev_ver][prev_hor] = dfs(row, 0, prev_ver, prev_hor, 0, 0);
}
int dfs(int row, int col, int prev_ver, int prev_hor, int now_ver, int now_hor) {
    while (1) {
        int re = inf;
        int col1 = 1 << col;
        if (col == m) {
            if (prev_hor != (1 << m) - 1)
                return inf;
            for (int i = 0; i < m; i++)
                if (e[row][i] == '.')
                    now_hor |= 1 << i;
            return sol(row + 1, now_ver, now_hor);
        }
        if (prev_ver & col1) {
            if (now_hor & col1)
                return inf;
            now_hor |= col1;
        }
        if (s[row][col] == '.') {
            if (!(prev_hor & col1))
                return inf;
            if (e[row][col] == '.')
                now_hor |= col1;
            col++;
            continue;
        }

        if (!(prev_hor & col1)) {
            if (s[row][col] != e[row - 1][col])
                return inf;
            if (prev_ver & col1)
                return 1 + dfs(row, col + 1, prev_ver, prev_hor | col1, now_ver, now_hor);
            prev_hor |= col1;
            col++;
            continue;
        }
        if (s[row][col] == e[row][col] && !(prev_ver & col1) && !(now_hor & col1))
            re = min(re, dfs(row, col + 1, prev_ver, prev_hor, now_ver, now_hor | col1));

        if (col < m - 1 && s[row][col] == e[row][col + 1])
            re = min(re, dfs(row, col + 1, prev_ver, prev_hor, now_ver, now_hor | (col1 << 1)));

        if (col && s[row][col] == e[row][col - 1] && !(now_hor & (col1 >> 1))) {
            if (!(prev_ver & col1) && (now_hor & col1))
                re = min(re, 1 + dfs(row, col + 1, prev_ver, prev_hor, now_ver, now_hor | (col1 >> 1)));
            else
                re = min(re, dfs(row, col + 1, prev_ver, prev_hor, now_ver, now_hor | (col1 >> 1)));
        }
        if (row < n - 1 && s[row][col] == e[row + 1][col])
            re = min(re, dfs(row, col + 1, prev_ver, prev_hor, now_ver | col1, now_hor));
        return re;
    }
}