hdu 1175 dfs

背景：数次超时，数次wa，dfs还是存在代码不规范的情况，什么时候回溯没有考虑清楚。后来看了模板化的搜索写法，发现我一直没有用过visit[M][M]标记访问过的点，而是直接在原图上标记，这样是节约内存但是，容易出错！

思路：这个转向题最大的特点是，创建了一个结构体，即有转向数count，也有上次走来的方向up，一旦up和这次的方向数不一样，count就加一（我的代码少考虑了，起点和终点在同一点的情况，但数据没有这种，所以侥幸过了，要是有这样的数据，得找好久才能找出错点，起点和终点是同一点的情况，以后写搜索都得注意了）。

关于bfs的解法：这个题开始也可以想到bfs解法，但是有一点就是bfs不能保证从一点到下一点是转向最少的点啊，网上有人通过改变转向的次序，而夺过数据水过。后来看到正确写法是用三维标记数组：visit[1009][1009][4] 要保证每一个位置的四个方向都遍历了。

//hdu 1175
#include <iostream>
#include<cstdio>
#include<cstring>
#define M 1009
using namespace std;
int diagram[M][M],n,m,query,dir[4][2]={1,0,-1,0,0,-1,0,1},ans;
struct place{int x,y,up,count;}s,temp1,temp2,e;
void dfs(place temp1);

void scan(void){
     for(int i=1;i <= n;i++){
        for(int j=1;j <= m;j++){
            scanf("%d",&diagram[i][j]);
        }
     }
     scanf("%d",&query);
}


int main(void){
    while(scanf("%d%d",&n,&m),n*n+m*m){
        scan();
        while(query--){
            ans=M;
            scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y);
            s.count=0;
            s.up=-1;
            if(diagram[s.x][s.y] != diagram[e.x][e.y] || !diagram[s.x][s.y]) ans=M;    //终点棋子和起点棋子不一样，或一样都为0，直接输出no
            else dfs(s);
            if(ans <= 2) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

void dfs(place temp1){
     if(temp1.x == e.x && temp1.y == e.y){     //判断是否达到终点。
        if(temp1.count < ans) ans=temp1.count;
        return;
     }
     int key=diagram[temp1.x][temp1.y];    //回溯记录
     if(!key) diagram[temp1.x][temp1.y]=-M;
     for(int i=0;i < 4;i++){
         temp2.x=temp1.x+dir[i][0];
         temp2.y=temp1.y+dir[i][1];
         temp2.up=i;
         if(i != temp1.up && temp1.up != -1) temp2.count=temp1.count+1;
         else temp2.count=temp1.count;    //判断是否转向
         if(temp2.count > 2 || temp2.x < 1 || temp2.x > n || temp2.y < 1 || temp2.y > m) continue;
         if(temp2.count == 2 && (temp2.x != e.x && temp2.y != e.y)) continue;    //对于已经转了两次弯的，不能再转弯了，剪枝。
         if(diagram[temp2.x][temp2.y] == 0 || (temp2.x == e.x && temp2.y == e.y)){
             dfs(temp2);
             if(ans <= 2){diagram[temp1.x][temp1.y]=key;return;}    //核心剪枝：一旦找到满足条件的路径就跳出所有循环，跳出循环之前，必须要回溯。
         }
     }
     diagram[temp1.x][temp1.y]=key;    //回溯
     return;
}

hdu 1175 dfs

原文：http://blog.csdn.net/jibancanyang/article/details/44274827