改了一下，但是还是输出-1
#include <stdio.h>
#include <stdlib.h>
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int visit[10][10][10];
int ans=0;
int judge(int x,int y,int n,int m,int map[10][10])
{
    if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]==1)
    return 1;
    return 0;
}
void dfs(int map[10][10],int n,int m,int startx,int starty,int endx,int endy)
{
    int queue[100][4];
    int head=0,tail=1,x,y,xx,yy,step,i;
    memset(queue,0,sizeof(queue));
    queue[0][0]=startx;
    queue[0][1]=starty;
    queue[0][2]=0;
    queue[0][3]=6;
    while(head<tail)
    {
    x=queue[head][0];
    y=queue[head][1];
    step=queue[head][2];
    ans=queue[head][3];
    if(x==endx&&y==endy)
    {
    printf("%d\n",step);
    return step;
    }
    head++;
    for(i=0;i<4;i++)
    {
    xx=x+dx[i];
    yy=y+dy[i];
    if(judge(xx,yy,n,m,map)==1&&queue[head][3]>1&&visit[xx][yy][ans]==0)
    {
    queue[tail][0]=xx;
    queue[tail][1]=yy;
    queue[tail][2]=step+1;
    queue[tail][3]=ans-1;
    visit[xx][yy][ans]=1;
    tail++;
    }
    if(map[xx][yy]==4&&visit[xx][yy][ans]==0)
    {
    queue[tail][0]=xx;
    queue[tail][1]=yy;
    queue[tail][2]=step+1;
    queue[head][3]=6;
    visit[xx][yy][ans]=1;
    tail++;
    }
    }
    }
    printf("-1\n");
}
int main()
{
    int map[10][10],n,m,startx,starty,endx,endy;
    int i,j;
    memset(map,0,sizeof(map));
    memset(visit,0,sizeof(visit));
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    {
    scanf("%d",&map[i][j]);
    if(map[i][j]==2)
    startx=i,starty=j;
    if(map[i][j]==3)
    endx=i,endy=j;
    }
    dfs(map,n,m,startx,starty,endx,endy);
    system("pause");
    return 0;
}

map[endx][endy] == 3
所以，你上面的代码永远走不到终点

楼主为什么不用递归回溯？而且你的算法不能找到最短路径吧，因为只要找到一条路径你的 dfs() 就返回了，但是没办法保证找到的第一条路径就是最短的啊

BFS下来得出解必定是最优解

为什么？

啊，我明白了，的确是的。 恩～这个算法效率比较高

[ 本帖最后由 voidx 于 2011-4-24 20:58 编辑 ]

楼主以后多教教我
你做不做 的题