#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int cap = 500010;
int dist[510][510]; char map[510][510]; bool proc[510][510];
pair<int, int> queue[cap * 2]; int r, c, li, ri;
inline bool valid (int x, int y) { return x >= 0 && x <= r && y >= 0 && y <= c; }
inline void que_add (int x, int y, int v)
{
if (dist[x][y] < 0 || v < dist[x][y])
{
dist[x][y] = v;
if (li == ri || v > dist[queue[li].first][queue[li].second]) queue[ri++] = make_pair(x, y);
else queue[--li] = make_pair(x, y);
}
}
int main ()
{
freopen("cir.in", "r", stdin);
freopen("cir.out", "w", stdout);
int kase; for (scanf("%d", &kase); kase; --kase)
{
scanf("%d %d", &r, &c);
if ((r + c) % 2)
{
for (int i = 0; i < r; i++) scanf("%s", map[i]);
printf("NO SOLUTION\n");
}
else
{
for (int i = 0; i < r; i++) scanf("%s", map[i]);
li = ri = cap; queue[ri++] = make_pair(0, 0);
memset(dist, -1, sizeof dist), dist[0][0] = 0;
memset(proc, false, sizeof proc);
while (li != ri)
{
int cx = queue[li].first, cy = queue[li].second; ++li;
if (valid(cx - 1, cy - 1))
{
if (map[cx - 1][cy - 1] == '\\') que_add(cx - 1, cy - 1, dist[cx][cy]);
else que_add(cx - 1, cy - 1, dist[cx][cy] + 1);
}
if (valid(cx - 1, cy + 1))
{
if (map[cx - 1][cy] == '/') que_add(cx - 1, cy + 1, dist[cx][cy]);
else que_add(cx - 1, cy + 1, dist[cx][cy] + 1);
}
if (valid(cx + 1, cy - 1))
{
if (map[cx][cy - 1] == '/') que_add(cx + 1, cy - 1, dist[cx][cy]);
else que_add(cx + 1, cy - 1, dist[cx][cy] + 1);
}
if (valid(cx + 1, cy + 1))
{
if (map[cx][cy] == '\\') que_add(cx + 1, cy + 1, dist[cx][cy]);
else que_add(cx + 1, cy + 1, dist[cx][cy] + 1);
}
}
printf("%d\n", dist[r][c]);
}
}
return 0;
}
信息学奥赛一本通 NOIP500+第1部分 （588个子文件） 
segment.bak 647B t.bat 320B test.bat 277B STICK.BAT 264B prod.BAT 263B RIDDLE.BAT 260B paint.bat 259B FISH.BAT 257B test.bat 253B TEST.BAT 246B cir.cpp 2KB divide_b.cpp 673B zju1937.cpp 639B divide_a.cpp 453B ENTER 2B enter 2B ENTER 2B ENTER 2B ENTER 2B ENTER 2B ENTER 2B
segment.exe 60KB divide_b.exe 57KB gen.exe 32KB candy.exe 17KB segment10.in 14.09MB segment8.in 14.09MB segment9.in 14.09MB 7.in 11.09MB 9.in 9.78MB 10.in 8.27MB candy8.in 8.02MB candy4.in 7.88MB 8.in 7.35MB candy9.in 6.68MB candy3.in 5.82MB grz81.in 5.42MB candy7.in 5.03MB grz82.in 4.21MB candy5.in 3.79MB grz91.in 3.34MB candy6.in 2.86MB grz45.in 1.91MB segment7.in 1.41MB curves10.in 1.32MB curves6.in 1.31MB curves9.in 1.31MB curves7.in 1.31MB curves8.in 1.31MB segment6.in 1.22MB grz7.in 1.2MB 5.in 1.01MB cir9.in 975KB aggr.7.in 966KB cir8.in 918KB 6.in 847KB cir7.in 679KB aggr.6.in 675KB divide_a5.in 577KB divide_b5.in 577KB divide_a3.in 478KB divide_b3.in 478KB cir6.in 464KB cowfnc.8.in 434KB divide_a4.in 285KB divide_b4.in 285KB grz6.in 269KB cowfnc.14.in 195KB cowfnc.13.in 176KB cowfnc.12.in 176KB aggr.5.in 158KB trees5.in 135KB 3.in 94KB trees0.in 81KB trees11.in 79KB trees12.in 79KB trees9.in 76KB trees10.in 76KB 4.in 75KB grz5.in 69KB trees7.in 68KB cowfnc.11.in 67KB trees8.in 63KB grz4.in 58KB trees6.in 58KB cowfnc.7.in 43KB cir5.in 39KB cowfnc.10.in 19KB cowfnc.9.in 19KB segment5.in 14KB curves3.in 14KB curves2.in 14KB curves1.in 14KB curves5.in 14KB curves4.in 14KB prod12.in 14KB trees4.in 11KB segment3.in 11KB segment4.in 11KB 1.in 8KB共 588 条
- 1
- 2
- 3
- 4
- 5
- 6
资源评论
zhxhcj2019-10-16好东西，正在弄这个，正式需要的
njzdl2019-03-31为什么不一起？
