题意——
一个n*m的地图，从左上角走到右下角。
这个地图是一个01串，要求我们行走的路径形成的01串最小。
注意，串中最左端的0全部可以忽略，除非是一个0串，此时输出0。
例：
3 3
001
110
001
此图的最短路径为101。
输入——
第一行输入一个整数t，表示共有t组数据。
接下来每组第一行输入两个整数n, m。表示地图的长和宽。
接下来n行，每行m个字符。字符只有0或1。
输出——
输出一个字符串，表示最短路径。
这道题刚开始用了优先队列+大数写的bfs，然后无限爆tle，后来想了想——
首先，用优先队列时，每个节点入队的时间复杂度为log2(k)，其中k为当前队列的长度。
其次，大数每次乘2的操作都要len次，每次在入队时和其他节点比较时还可能要len次，len为数的长度。
而地图最大是1000*1000的，总共的时间复杂度粗略算一下要10^6*log2(10^3)*40，刚好卡在时限上了，再乘上一个常数，就超时了，再乘上t，更超时了。
不能用优先队列，用普通队列，怎么写想了好久，在比赛结束之后又看了一下题解，发现大概有一下几种解法——
- 先搜出来从起点出发的所有0，此时起点必须是0，用bfs向4个方向搜；然后从所有0出发，寻找到终点的点，用bfs向下或向右走；然后再从终点出发，往回走，用dfs；然后就看不懂了……
- 先搜出来从起点出发的所有0，此时起点必须是0，用bfs向4个方向搜；然后在这些0中选取行号和列号相加最大的点，因为这些点距离终点最近，可以得知，这些点在同一斜行，然后从这些点所在的斜行的下一斜行开始，一行一行向下进行递推——优先选取0，对本斜行中选取的字符标记，然后对下一斜行进行递推时，只考虑可以从标记点走到的点。
当然，当对0进行搜索时，已经搜到终点，那么输出0就可以了。
我用的是第二种方法。
耗时109ms，内存4520k。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std; const int N = ; struct Node
{
int x, y;
}; int dir[][] = {{, }, {, }, {-, }, {, -}};
int sxy[N*N];
char mp[N][N];
bool vis[N][N];
int n, m, t, rt, k;
queue<Node> q0; int bfs0()
{
Node p, ps;
p.x = p.y = ;
vis[][] = ;
if(mp[][] == '') q0.push(p);
else
{
sxy[] = ;
k = ;
printf("");
return ;
}
k = ;
while(!q0.empty())
{
p = q0.front();
q0.pop();
sxy[k++] = p.x+p.y;
if(p.x == n- && p.y == m-) return ;
for(int i = ; i < ; i++)
{
int sx = p.x+dir[i][];
int sy = p.y+dir[i][];
if(sx >= && sx < n && sy >= && sy < m && !vis[sx][sy] && mp[sx][sy] == '')
{
vis[sx][sy] = ;
ps.x = sx;
ps.y = sy;
q0.push(ps);
}
}
}
return ;
} void sroot()
{
rt = ;
for(int i = ; i < k; i++) if(rt < sxy[i]) rt = sxy[i];
} void getans()
{
for(int i = rt+; i <= m+n-; i++)
{
k = ;
if(i >= n-) k = i-n+;
int tmp = ;
for(int j = k; j < m && j <= i; j++)
{
if((i-j- >= && i-j < n && j >= && vis[i-j-][j])
|| (i-j >= && i-j < n && j- >= && vis[i-j][j-]))
{
int mid = mp[i-j][j]-'';
tmp = tmp < mid ? tmp : mid;
}
}
printf("%d", tmp);
for(int j = k; j < m && j <= i; j++)
{
if((i-j- >= && i-j < n && j >= && vis[i-j-][j])
|| (i-j >= && i-j < n && j- >= && vis[i-j][j-]))
{
if(mp[i-j][j]-'' == tmp) vis[i-j][j] = ;
}
}
}
printf("\n");
} void init()
{
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++) scanf("%s", mp[i]);
memset(vis, , sizeof(vis));
while(!q0.empty()) q0.pop();
} int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
scanf("%d", &t);
while(t--)
{
init();
if(bfs0()) printf("0\n");
else
{
sroot();
getans();
}
}
return ;
}