1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
const int mX[] = {-1, 0, 1, 0};
const int mY[] = {0, 1, 0, -1};
int n, m, k;
char board[N][N];
int dp[N][N];
int dis[15][15], locX[15], locY[15];
int dpp[1 << 15][15];
bool bfs(int d) {
  deque <tuple<int, int> > de;
  memset(dp, 0x7f, sizeof dp);
  dp[locX[d]][locY[d]] = 0;
  de.emplace_back(locX[d], locY[d]);
  while (!de.empty()) {
    int x, y;
    tie(x, y) = de.front();
    de.pop_front();
    for (int i = 0; i < 4; ++i) {
      int xx = x + mX[i], yy = y + mY[i];
      if (xx < 0 || xx >= n || yy < 0 || yy >= m)
        continue;
      if (board[xx][yy] == '1')
        continue;
      if (dp[xx][yy] > dp[x][y] + 1) {
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX