# 3299: [USACO2011 Open]Corn Maze玉米迷宫

## 3299: [USACO2011 Open]Corn Maze玉米迷宫

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 137  Solved: 59

[Submit][Status][Discuss]

## Sample Input

5 6 ###=## #.W.## #.#### #.@W## ######

3

## Source

Silver

``` 1 const dd:array[1..4,1..2] of longint=((1,0),(-1,0),(0,-1),(0,1));
2 var
3    i,j,k,l,m,n,x0,y0,x1,y1,x,y,f,r:longint;
4    a,b:array[0..1000,0..1000] of longint;
5    tr:array[2..27,1..4] of longint;
6    d:array[0..1000000,1..2] of longint;
7    ch:char;
8 procedure trans(z:longint;var x,y:longint);
9          begin
10               if (z<2) or (z>27) then exit;
11               if (tr[z,1]=x) and (tr[z,2]=y) then
12                  begin
13                       x:=tr[z,3];y:=tr[z,4];
14                  end
15               else if (tr[z,3]=x) and (tr[z,4]=y) then
16                    begin
17                         x:=tr[z,1];y:=tr[z,2];
18                    end;
19          end;
20 begin
22      fillchar(a,sizeof(a),-1);
23      fillchar(tr,sizeof(tr),0);
24      for i:=1 to n do
25          begin
26               for j:=1 to m do
27                   begin
29                        case upcase(ch) of
30                             '#':a[i,j]:=1;
31                             '.':a[i,j]:=0;
32                             '=':begin
33                                      x1:=i;y1:=j;
34                                      a[i,j]:=0;
35                             end;
36                             '@':begin
37                                      x0:=i;y0:=j;
38                                      a[i,j]:=1;
39                             end;
40                             'A'..'Z':begin
41                                           a[i,j]:=ord(ch)-63;
42                                           if tr[a[i,j],1]=0 then
43                                              begin
44                                                   tr[a[i,j],1]:=i;
45                                                   tr[a[i,j],2]:=j;
46                                              end
47                                           else
48                                               begin
49                                                    tr[a[i,j],3]:=i;
50                                                    tr[a[i,j],4]:=j;
51                                               end;
52                             end;
53                        end;
54                   end;
56          end;
57      f:=1;r:=2;d[1,1]:=x0;d[1,2]:=y0;b[x0,y0]:=1;
58      while f<r do
59            begin
60                 for i:=1 to 4 do
61                     begin
62                          x:=d[f,1]+dd[i,1];
63                          y:=d[f,2]+dd[i,2];
64                          if (x<1) or (x>n) or (y<1) or (y>m) then continue;
65                          if abs(a[x,y])=1 then continue;
66                          trans(a[x,y],x,y);
67                          if b[x,y]=0 then
68                             begin
69                                  b[x,y]:=b[d[f,1],d[f,2]]+1;
70                                  d[r,1]:=x;d[r,2]:=y;
71                                  if (x=x1) and (y=y1) then
72                                     begin
73                                          writeln(b[x,y]-1);
74                                          halt;
75                                     end;
76                                  inc(r);
77                             end;
78                     end;
79                 inc(f);
80            end;
81 end.```

0 条评论

• ### 算法模板——线段树9（区间加+区间求和+区间方和）

如题，实现一个程序，输入N个数，进行如下维护： 1.1 x y 求[x,y]区间的和 2.2 x y 求[x,y]区间的平方和 3.3 x y z 将[x,y]...

• ### 从Hash Killer I、II、III论字符串哈希

首先，Hash Killer I、II、III是BZOJ上面三道很经典的字符串哈希破解题。当时关于II，本人还琢磨了好久，但一直不明白为啥别人AC的代码都才0....

• ### 算法模板——线性筛素数

实现功能：如题，筛出1——N内的所有素数 原理：如phile神犇所言，这次的才算是真正意义上的线性筛素数，其精髓在于if (i mod a[j])=0 then...

• ### 学习笔记：delphi多线程知识

最近一直在温习旧的知识，刚好学习了一下Java的线程安全方面的知识，今天想起之前一直做的Delphi开发，所以还是有必要温习一下，看看这些不同的编程语言有什么不...

• ### 如何对多行单次update接口进行压测

上次聊到如何对单行多次update进行压测，主要是为了解决单线程中请求参数如何每次都跟上次不一样这个难点。

• ### 国内大厂都在使用哪些移动跨平台框架

自从移动应用开发兴起以来，不少公司和开发者就在不断的探索移动跨平台开发技术，以适应移动应用高速迭代的需求 。纵观当前的移动跨平台方案，总结一下无外乎三大类：一种...

• ### 为什么分库分表后不建议跨分片查询

在这篇文章中提到了一个场景，即电商的订单。我们都知道订单表有三大主要查询：基于订单ID查询，基于商户编号查询，基于用户ID查询。且那篇文章给出的方案是基于订单I...

• ### Java多线程：还不懂线程池吗？一文带你彻底搞懂！

总体来说，线程池有如下的优势： （1）降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。 （2）提高响应速度。当任务到达时，任务可以不需要...

• ### Java中可重入锁ReentrantLock原理剖析

本文首先介绍Lock接口、ReentrantLock的类层次结构以及锁功能模板类AbstractQueuedSynchronizer的简单原理，然后通过分析Re...