强烈推荐此题！
一种巧妙的DP，称为插头DP。每个格子是一个阶段，状态是通过这个格子的右边一个格子的左边和上边的S形折线（共由m+1条线段组成）上的3进制数。
这是题目的第一个sample，我把行、列都从1开始编号，原始图设为g，红线表示状态f[2][2][(100221)3]。
状态设计好了，状态转移也就不是难事了。根据g[i][j ＋ 1]的值来确定状态转移的方式。
我是用顺推的转移，不大好表述，不懂的话看看代码，再看看图，想想就能明白。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-9-24 19:35:22
File Name: pku3133.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 10;
const int mask[11] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};
int g[maxn][maxn];
char f[maxn + 1][maxn][59049];
int n, m;
int pow3m;
inline int get_bit(int x, int k)
{
return x % mask[k + 1] / mask[k];
}
inline int set_bit(int x, int k)
{
return x - get_bit(x, k) * mask[k] - get_bit(x, k + 1) * mask[k + 1];
}
int dp()
{
pow3m = mask[m + 1];
memset(f, 0x7F, sizeof(f));
f[1][0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < m; j++)
for (int k = 0; k < pow3m; k++) if (f[i][j][k] != 0x7F)
{
int bit_j = get_bit(k, j);
int bit_j1 = get_bit(k , j + 1);
int pre_bit = set_bit(k, j);
if (g[i][j + 1] == 1)
{
if (bit_j == 0 && bit_j1 == 0)
f[i][j + 1][k] <?= f[i][j][k];
}
else if (g[i][j + 1] == 2)
{
if (bit_j + bit_j1 == 1)
f[i][j + 1][pre_bit] <?= f[i][j][k] + 1;
if (bit_j + bit_j1 == 0)
{
f[i][j + 1][pre_bit + mask[j]] <?= f[i][j][k] + 1;
f[i][j + 1][pre_bit + mask[j + 1]] <?= f[i][j][k] + 1;
}
}
else if (g[i][j + 1] == 3)
{
if (bit_j == 0 && bit_j1 == 2 || bit_j == 2 && bit_j1 == 0)
f[i][j + 1][pre_bit] <?= f[i][j][k] + 1;
if (bit_j + bit_j1 == 0)
{
f[i][j + 1][pre_bit + 2 * mask[j]] <?= f[i][j][k] + 1;
f[i][j + 1][pre_bit + 2 * mask[j + 1]] <?= f[i][j][k] + 1;
}
}
else
{
if (bit_j == 1 && bit_j1 == 0 || bit_j == 0 && bit_j1 == 1)
{
f[i][j + 1][pre_bit + mask[j]] <?= f[i][j][k] + 1;
f[i][j + 1][pre_bit + mask[j + 1]] <?= f[i][j][k] + 1;
}
if (bit_j == 0 && bit_j1 == 2 || bit_j == 2 && bit_j1 == 0)
{
f[i][j + 1][pre_bit + 2 * mask[j]] <?= f[i][j][k] + 1;
f[i][j + 1][pre_bit + 2 * mask[j + 1]] <?= f[i][j][k] + 1;
}
if (bit_j == 1 && bit_j1 == 1 || bit_j + bit_j1 == 4)
f[i][j + 1][pre_bit] <?= f[i][j][k] + 1;
if (bit_j + bit_j1 == 0)
{
f[i][j + 1][pre_bit] <?= f[i][j][k];
f[i][j + 1][pre_bit + mask[j] + mask[j + 1]] <?= f[i][j][k] + 1;
f[i][j + 1][pre_bit + 2 * mask[j] + 2 * mask[j + 1]] <?= f[i][j][k] + 1;
}
}
}
for (int k = 0; k < pow3m / 3; k++)
f[i + 1][0][k * 3] = f[i][m][k];
}
if (f[n][m][0] == 0x7F)
return 0;
else
return f[n][m][0] - 2;
}
int main()
{
while (scanf("%d%d", &n, &m), n + m != 0)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &g[i][j]);
printf("%d\n", dp());
}
return 0;
}