题意
给一张网格图，网格之间会存在墙和门，你知道有且仅有一扇门打不开，但是不知道是哪一扇门，输出你能保证的从左上角走到右下角的步数的最小值。
(n,mle 30)
解法
想对了一半，后面一半没想到二分。
其实这就是，找到一条最佳的策略路径，使得路径上任意一步不能走的总步数的最大值最小。
其实很容易发现，当你试图打开一扇门失败之后，你接下来要走的最短步数，设它为(dis[x][y])。
于是，对于一条给定路径，可以很快计算这个路径代价，于是可以写暴搜，于是可以TLE。
然后发现二分就很有用了，其实这道题跟一个最大权最小的最小的这种题类似。
当我们确定了最大权不超过多少的时候，对于小于等于最大权的走法，都可以任意取用。
于是我们二分一个最大值，对于每个点(d + dis[x][y] <= limit)的路径都可以走，于是BFS一下check正确性就行了。
emm怎么求(dis)？
枚举哪扇门坏了，然后在不能走这扇门的前提下跑一个到每个点的最短路就行了，可能要增加一点dis的维度。
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pt(x) cout << x << endl;
#define Mid ((l + r) / 2)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read() {
char c; int num, f = 1;
while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
return f * num;
}
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int n, m, cw[39][39], rw[39][39];
int dis[39][39][2][39][39], vis[39][39];
void cal(int a, int b, char c) {
queue<pii> q; q.push({n, m});
dis[a][b][c == 'c'][n][m] = 0;
while(q.size()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if(xx <= 0 || y <= 0 || xx > n || yy > m) continue;
if(dis[a][b][c == 'c'][xx][yy] != 0x3f3f3f3f) continue;
if(i == 0 && ((c == 'c' && a == x && b == y) || (cw[x][y] == 1))) continue;
if(i == 1 && ((c == 'c' && a == xx && b == yy) || (cw[xx][yy] == 1))) continue;
if(i == 2 && ((c == 'r' && a == x && b == y) || (rw[x][y] == 1))) continue;
if(i == 3 && ((c == 'r' && a == xx && b == yy) || (rw[xx][yy] == 1))) continue;
dis[a][b][c == 'c'][xx][yy] = dis[a][b][c == 'c'][x][y] + 1;
q.push({xx, yy});
}
}
}
int check(int limit) {
queue<pii> q; q.push({1, 1});
memset(vis, -1, sizeof(vis)); vis[1][1] = 0;
while(q.size()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if(x == n && y == m) return true;
for(int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;
if(i == 0 && (cw[x][y] == 1)) continue;
if(i == 1 && (cw[xx][yy] == 1)) continue;
if(i == 2 && (rw[x][y] == 1)) continue;
if(i == 3 && (rw[xx][yy] == 1)) continue;
int d = vis[x][y];
if(vis[xx][yy] != -1) continue;
if(i == 0 && d + dis[x][y][1][x][y] > limit) continue;
if(i == 1 && d + dis[xx][yy][1][x][y] > limit) continue;
if(i == 2 && d + dis[x][y][0][x][y] > limit) continue;
if(i == 3 && d + dis[xx][yy][0][x][y] > limit) continue;
vis[xx][yy] = vis[x][y] + 1;
q.push({xx, yy});
}
}
return false;
}
void work() {
if(n == 0 && m == 0) exit(0);
memset(dis, 0x3f, sizeof(dis));
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) cw[i][j] = read();
for(int j = 1; j <= m; j++) rw[i][j] = read();
}
for(int i = 1; i < m; i++) cw[n][i] = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j < m; j++)
cal(i, j, 'c');
for(int i = 1; i < n; i++)
for(int j = 1; j <= m; j++)
cal(i, j, 'r');
int l = 1, r = 1000;
while(l <= r) {
if(check(Mid)) r = Mid - 1;
else l = Mid + 1;
}
printf("%d
", l == 1001 ? -1 : l);
}
signed main()
{
while(~scanf("%d%d", &n, &m)) work();
return 0;
}