题目链接：
题目描述：
有一个n*m由0 or 1组成的矩形，探险家要从(1,1)走到(n, m),可以向上下左右四个方向走，但是探险家就是不走寻常路，他想让他所走的路线上的0/1组成的二进数最小，现在要为矫情无比的探险家找最优路径咯。
解题思路：
对于二进制数，前导零是对数字大小没有任何影响的。当到不得不走1的时候就只能向下，或者向右走了。所以先搜索出来一直走零，能走到的最靠近终点的位置，然后在类似搜索，找出最优路径。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = ;
struct node
{
int x, y;
};
char maps[maxn][maxn];
bool vis[maxn][maxn];
int dir[][] = {,, ,, -,, ,-};
int x, y, n, m;
bool Ok (int x, int y)
{
if (x< || y< || x>=n || y>=m)
return false;
return true;
}
void bfs ()
{
node p, q;
p.x = x, p.y = y;
queue <node> Q;
Q.push (p);
while (!Q.empty())
{
p = Q.front();
Q.pop();
for (int i=; i<; i++)
{
q.x = p.x + dir[i][];
q.y = p.y + dir[i][];
if (Ok(q.x, q.y) && !vis[q.x][q.y])
{
vis[q.x][q.y] = true;
if (maps[q.x][q.y] == '')
Q.push (q);
if (x + y < q.x + q.y)
x = q.x, y = q.y;
}
}
}
}
int main ()
{
int t;
scanf ("%d", &t);
while (t --)
{
memset (vis, false, sizeof(vis));
vis[][] = true;
scanf ("%d %d", &n, &m);
for (int i=; i<n; i++)
scanf ("%s", maps[i]);
x = y = ;
if (maps[x][y] == '')
bfs ();
if (maps[x][y] == '')
putchar('');
else
{
bool nowflag = false;
putchar ('');
for (int i=x+y; i<n+m-; i++)
{
bool flag = false;
for (x=; x<=i; x++)
{
y = i - x;
if (!Ok(x, y) || !vis[x][y])
continue;
if (nowflag && maps[x][y]=='')
continue;
for (int j=; j<; j++)
{
int a = x + dir[j][];
int b = y + dir[j][];
if (!Ok(a, b))
continue;
vis[a][b] = true;
if (maps[a][b] == '')
flag = true;
}
}
nowflag = flag;
putchar (flag?'':'');
}
}
puts("");
}
return ;
}