题意：有一个n*m的矩阵，每个格子中有一个数字，或为0，或为1。有个人要从（1，1）到达（n，m），要求所走过的格子中的数字按先后顺序串起来后，用二进制的判断大小方法，让这个数字最小。前缀0不需要输出！！
思路：主要考虑的是BFS解决。
如果grid[1，1]=1，那么这个二进制的位数也就定下来了，是n+m-1，很好解决，每个格子就只能往下或者往右，否则长度一定超过n+m+1，必定不是最优。
如果grid[1，1]=0，那么可能会出现绕了一个S型到终点的结果为0而已。所以不能用老办法，要先预处理一下。处理方式是，用BFS将所有grid[1，1]可达的0点标记出来，找出其中距离终点最近的那些0点（可能多个），如果他们的下和右边的点为1，这些点都进队，再用上边方式BFS即可求得答案（上面只是1个起点，这边有多个起点，不影响正确性）。
答案在哪？其实在BFS时每一层只能是0点或者是1点，为什么呢？如果有0点的话，还需要选择1点的吗？别忘了二进制的位数是固定了，选0肯定比选1要好，则在没有0的情况下再选1的。 在遍历时按层遍历，遍历到的点先分到两个集合A0和B1中，择所需即可，所以在遍历第i层时第i位的答案也就决定了。这是剪枝！
注意考虑只有1个点，2个点和S形等各种情况。
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define pii pair<int,int>
#define LL unsigned long long
using namespace std;
const int N=;
int n, m;
char grid[N][N];
vector<int> ans;
int inq[N][N]; void BFS(deque<pii> &que)
{
ans.push_back();
while(!que.empty())
{
deque<pii> que0, que1; //两种到达的方式，只取其一
int siz=que.size();
for(int i=; i<siz; i++) //被更新的都是同一源头的。
{
int a=que.front().first;
int b=que.front().second;
que.pop_front(); if( a+<=n && !inq[a+][b] ) //下:要么你无路径可达，要么我比你小，我才更新你
{
if(grid[a+][b]=='') que0.push_back(make_pair(a+,b));
else que1.push_back(make_pair(a+,b));
}
if( b+<=m && !inq[a][b+] ) //右
{
if(grid[a][b+]=='') que0.push_back(make_pair(a,b+));
else que1.push_back(make_pair(a,b+));
}
inq[a+][b]=inq[a][b+]=;
} if(!que0.empty()) ans.push_back();
else ans.push_back(); if(!que0.empty()) que.insert(que.end(), que0.begin(), que0.end() );
else que.insert(que.end(), que1.begin(), que1.end() );
}
} int cal()
{
memset(inq, , sizeof(inq)); deque<pii> que;que.push_back( make_pair(,));
if(grid[][]=='') //若起点为0，找到所有离终点最近的前缀0
{
inq[][]=;
while(!que.empty())
{
int siz=que.size();
for(int i=; i<siz; i++) //按层来BFS，按层记录最优答案
{
int a=que.front().first;
int b=que.front().second;
que.pop_front(); if(a+<=n && !inq[a+][b] && grid[a+][b]=='') que.push_back(make_pair(a+,b));
if(a-> && !inq[a-][b] && grid[a-][b]=='') que.push_back(make_pair(a-,b)); if(b+<=m && !inq[a][b+] && grid[a][b+]=='') que.push_back(make_pair(a,b+));
if(b-> && !inq[a][b-] && grid[a][b-]=='') que.push_back(make_pair(a,b-)); inq[a+][b]=inq[a-][b]=inq[a][b+]=inq[a][b-]=; //防止重复进队
}
}
int min_dis=INF;
for(int i=; i<=n; i++) //求最近的0距离终点的最小距离
{
for(int j=; j<=m; j++)
{
if(inq[i][j]&&grid[i][j]=='')
min_dis=min(min_dis, n+m-j-i);
}
}
if(grid[n][m]=='' && min_dis==) return ; //有0路可达终点
for(int i=; i<=n; i++) //扫出距离为min_dis的所有0点
for(int j=; j<=m; j++)
if(inq[i][j] && grid[i][j]=='' && min_dis==n+m-j-i && n+m-i-j!= )
que.push_back(make_pair(i,j)); memset(inq,,sizeof(inq));
int siz=que.size();
for(int i=; i<siz; i++) //将所有0点的下和右为1的点进队
{
int a=que.front().first;
int b=que.front().second;
que.pop_front();
if(a+<=n&&!inq[a+][b]&&grid[a+][b]=='') que.push_back(make_pair(a+,b));
if(b+<=m&&!inq[a][b+]&&grid[a][b+]=='') que.push_back(make_pair(a,b+));
inq[a+][b]=inq[a][b+]=;
}
}
BFS(que);
return ans.size();
} int main()
{
freopen("input.txt", "r", stdin);
int t, a, b;
char c;
cin>>t;
while(t--)
{
ans.clear();
scanf("%d %d",&n,&m); for(int i=; i<=n; i++) //输入要注意
for(int j=; j<=m; j++)
{
c=getchar();
if(c==''||c=='' ) grid[i][j]=c;
else j--;
}
int s=cal();
if(s==) printf("");
else for(int i=; i+<ans.size(); i++) printf("%d",ans[i]);//最后一个数字多余
printf("\n");
}
return ;
}
AC代码