题意是：入口：地图的左上角，出口，地图的右上角，求所经过的路径的二进制数最小
照着题解敲了一遍
思路是：首先 二进制 的 位数 越小 越好，其次 二进制的前缀零越多 表示 值越小
首先 在前缀是0的情况下走到最远（最远的定义是 当前坐标是 i , j 则 在保证 位数越小的情况下 则 还剩下 n-i + m-j 的路要走）
剩下的路 必须 向 右走 或者向 下 走，然后 在 其中 选取 0 尽量 多的 路
代码：非原创！！！（from 多校题解）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue> using namespace std;
const int MAXN = +;
bool vis[MAXN][MAXN];
char graph[MAXN][MAXN];
int n,m;
int dr[] = {,,,-};
int dc[] = {,-,,};
struct Node{
int x,y;
}; void bfs(){
memset(vis,,sizeof(vis));
vis[][] = ;
queue<Node>q;
Node tmp;
tmp.x = ,tmp.y = ;
q.push(tmp);
int mx = ;
while(!q.empty()){
tmp = q.front();
q.pop();
if(graph[tmp.x][tmp.y] > ''){
continue;
}
for(int i = ;i < ;i++){
int xx = tmp.x + dr[i];
int yy = tmp.y + dc[i];
if(xx<||yy<||xx>n||yy>m || vis[xx][yy]){
continue;
}
// cout << "x = " << tmp.x << " y = " << tmp.y << endl;
Node tt;
tt.x = xx;
tt.y = yy;
vis[xx][yy] = ;
mx = max(mx,xx+yy);
// cout << "x = " << xx << " y = " << yy << endl << endl;;
q.push(tt);
}
}
if(vis[n][m] && graph[n][m] == ''){
printf("0\n");
return;
}
printf("");
for(int i = mx;i < m+n;i++){
char mi = '';
for(int j = ;j <= n;j++){
if(i-j > && i-j <= m && vis[j][i-j]){
mi = min(mi,graph[j+][i-j]); //向右走
mi = min(mi,graph[j][i-j+]);//向下走
}
}
printf("%c",mi);
for(int j = ;j <= n;j++){
if(i-j > && i-j <= m && vis[j][i-j]){
if(mi == graph[j+][i-j]){
vis[j+][i-j] = ;
}
if(mi == graph[j][i-j+]){
vis[j][i-j+] = ;
}
}
}
}
printf("\n");
}
int main(){
// freopen("input.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i = ;i <= n;i++){
scanf("%s",graph[i]+);
}
for(int i = ;i <= n+;i++){
graph[i][] = '';
graph[i][m+] = '';
}
for(int i = ;i < m+;i++){
graph[][i] = '';
graph[n+][i] = '';
}
bfs();
}
return ;
}