状压dp原理

const int N = 12, M = 1 << N;
LL f[N][M];
bool st[M];
int n, m;
int main() {
  while (cin >> n >> m, n || m) {
    memset(f, 0, sizeof f);
    for (int i = 0;i < 1 << n;++i) {//枚举1到n的每一个二进制数
      st[i] = true;//假设成立
      int cnt = 0;//当前这一段连续0的个数
      for (int j = 0; j < n;++j) {
        if ((i >> j) & 1) {//如果第j位为1 说明上一段连续的0已经结束
          if (cnt & 1)st[i] = false; // 如果为奇数 不成立
          cnt = 0; // 重置cnt
        }
        else cnt++;
      }
      if (cnt & 1)st[i] = false; //判断最后一段是否合法
    }
    f[0][0] = 1;
    for (int i = 1;i <= m;++i) {//枚举每一列
      for (int j = 0;j < 1 << n;++j) {//枚举当前列的所有情况
        for (int k = 0;k < 1 << n;++k) {//枚举前一列的所有情况
          if ((j & k) == 0 && st[j | k])//如果没有冲突并且所有连续的空格为偶数
            f[i][j] += f[i - 1][k]; //更新状态
        }
      }
    }
    cout << f[m][0] << endl;;//所有第m列没有方格出来的方案数即为答案
  }
  return 0;
}

const int N = 21, M = 1 << N;
int f[M][N];
int mp[N][N];
int main() {
  int n;cin >> n;
  for (int i = 0; i < n;++i) { //读入图
    for (int j = 0; j < n;++j) {
      cin >> mp[i][j];
    }
  }
  memset(f, 0x3f, sizeof f);
  f[1][0] = 0; // 只经过一个点时 距离为0
  for (int i = 0;i < 1 << n;++i) { //状态为i
    for (int j = 0; j < n;++j) { // 以j为终点
      if (i >> j & 1)//经过了j这一点的状态才有意义
        for (int k = 0; k < n;++k) //枚举从哪一个点转移过来
          if (i - (1 << j) >> k & 1) //没有经过j并且终点为k
            f[i][j] = min(f[i][j], f[i - (1 << j)][k] + mp[k]     [j]);
    }
  }
  cout << f[(1 << n) - 1][n - 1] << endl; //每一个点都经过 且终点为n-1
  return 0;
}