强烈推荐此题!
一种巧妙的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;
}