这是往年校赛的一道题，最开始做这道题的时候还没有系统的学习过搜索，用了C语言学的回溯法尝试，毫无疑问的TLE；

学习了DFS之后，自己的剪枝功力不够，又是TLE，最后学了BFS之后，哇，终于做出来了，别提多开心了，然后意识到这道题其实很简单的，剋以用BFS标记法和更改步数法（更改最小消耗），后来发现这种题也可以建图跑迪杰斯特拉做；

BFS标记法：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 100 + 5;int mat[N][N];bool visit[N][N];typedef struct node{    int x,y,val;    bool operator < (const node x)const {        return val > x.val;    }}Node;const int dir[4][2] = {
    {
    1,0},{-1,0},{
    0,1},{
    0,-1}};int BFS(int n){    priority_queue
         
           Q;    Node t;    memset(visit,0,sizeof(visit));    int x=0,y=0,goalx=n-1,goaly=n-1,newx,newy;    t=(Node){x,y,mat[x][y]};    visit[x][y] = true;    Q.push(t);    while(!Q.empty()){        t = Q.top();Q.pop();        if(t.x == goalx && t.y == goaly) return t.val;        for(int d=0;d<4;d++){            newx = t.x + dir[d][0];            newy = t.y + dir[d][1];            if(newx>=0 && newx
          
           =0 && newy
          
         
        
       
      
     

BFS更改步数法：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 100+5;const int MaxSize = 1e5;const int INF = (1<<30);int mat[N][N];int Min[N][N];typedef struct node{    int x,y,val;    bool operator < (const node x) const {        return val > x.val;    }}Node;const int dir[4][2]={
    {
    1,0},{-1,0},{
    0,1},{
    0,-1}};int BFS(int n){   priority_queue
         
           Q;   int newx,newy,x=0,y=0,goalx= n-1,goaly=n-1;   Node t,s;   t.x = x,t.y = y,t.val = mat[0][0];   Min[x][y] = mat[x][y];   Q.push(t);   while(true){        t = Q.top();        if(t.x == goalx && t.y == goaly ) return t.val;        for(int d=0;d<4;d++){            newx = t.x+dir[d][0];            newy = t.y+dir[d][1];            if(newx>=0 && newx
          
           =0 && newy
          
         
        
       
      
     

建图跑迪杰斯特拉：

#include
     
      #include
      
       #include
       
        #define _cp(a,b)((a.val)<(b.val))using namespace std;const int MAXN = 100000;const int INF = (1<<30);const int N = 100 + 5;int mat[N][N],D[N*N];bool visit[N*N];int Size[N*N];typedef struct node{    short val,to;}Node;typedef Node elem_t;Node edge[N*N][4];const int dir[4][2]={
    {-1,0},{
    1,0},{
    0,1},{
    0,-1}};void Init(){    for(int i=0;i
        
         =0 && newx
         
          =0 && newy
          
           1 && _cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1); h[p] = e; } int del(elem_t &e){ if(!n) return 0; for(e=h[p=1],c=2;c
           
             D[u] + edge[u][j].val){ D[v] = D[u] +edge[u][j].val; t.to = v,t.val = D[v]; H.ins(t); } } } return D[n*n-1] + mat[0][0];}void Input_data(int n){ for(int i=0;i
           
          
         
        
       
      
     

双向BFS：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 100+5;const int MaxSize = 1e5;const int INF = (1<<30);int mat[N][N];struct visit{    int val,vis;}Min[N][N];typedef struct node{    int x,y,val;    bool operator < (const node x) const {        return val > x.val;    }}Node;const int dir[4][2]={
    {1,0},{-1,0},{0,1},{0,-1}};int BFS(int n){   priority_queue
         
           Q1,Q2;   int newx,newy,cnt,x=0,y=0,goalx= n-1,goaly=n-1,ans = INF;   Node t,s;   t.x = x,t.y = y,t.val = mat[0][0];   s.x = goalx,s.y = goaly,s.val = mat[goalx][goaly];   Min[x][y].vis = 1,Min[x][y].val = mat[x][y];   Min[goalx][goaly].vis = 2,Min[goalx][goaly].val = mat[goalx][goaly];   Q1.push(t);   Q2.push(s);   while(!Q1.empty()|| !Q2.empty()){    cnt = Q1.size();    while(cnt--){
             t = Q1.top(); Q1.pop();        if(t.x == goalx && t.y == goaly ) ans = min(ans,t.val);         //这里一定要注意，要拓展完才能确定最小值，不能相遇就跳出        for(int d=0;d<4;d++){
                 newx = t.x+dir[d][0];            newy = t.y+dir[d][1];            if(newx>=0 && newx
          
           =0 && newy
           
            =0 && newx
            
             =0 && newy
            
           
          
         
        
       
      
     

在这几种方法里，双向BFS和迪杰斯特拉耗时都是12ms，比其他两种BFS耗时都短，虽然说在这里使用迪杰斯特拉有点大材小用的意味，但是这种方法也去可以应用到其他问题上