額最近做的好像都是廣搜也...

貪吃蛇是我很早以前就接觸，現(xiàn)在才能看懂的..十分尷尬,

然后這兩題類型一樣，我就寫一起啦~

都是四個(gè)方向，然后把走的方向存下來最后一起輸出。

TOJ 3128 簡(jiǎn)單版貪吃蛇

描述

現(xiàn)在我們來簡(jiǎn)化蛇的身體，假設(shè)初始化的時(shí)候蛇的身體只有一個(gè)頭而已（呵，當(dāng)然是假設(shè)的），那么蛇去吃食物的時(shí)候就不必考慮碰到自己的身體了。例：

5 5.....S....###.#E....#####
那么從S到E最短的走法是EEESSWWW。說明：N（north），S（south），W（west），E（east）。如果吃不到食物就輸出Can't eat it!注意：路徑是最短的走的。
輸入
輸入數(shù)據(jù)有多組，每組輸入的第一行是兩個(gè)正整數(shù)R，C，表示行和列，3=<R，C<=100，下面輸入R行C列的矩陣。
輸入保證合法。
輸出
每行輸出最短的走法。
樣例輸入
5 5.....S....###.#E....#####
樣例輸出
EEESSWWW
#include <cstring>#include <iostream>#include <queue>#include <cstdio>using namespace std;int n,m,dir[4][2]= {-1,0,1,0,0,-1,0,1};int vis[100][100],ex,ey,sx,sy,flag;char map[100][100];struct node{    int x;    int y;    char c[101];};void bfs(int x,int y){    node a,p,b;    int i;    vis[x][y]=1;    a.x=x;    a.y=y;    memset(a.c,'/0',sizeof(a.c));    queue<node>Q;    Q.push(a);    while(!Q.empty())    {        b=Q.front();        Q.pop();        if(map[b.x][b.y]=='E')        {            flag=1;            PRintf("%s/n",b.c);            return;        }        for(i=0;i<4;i++)        {            p=b;            p.x=p.x+dir[i][0];            p.y=p.y+dir[i][1];            if(map[p.x][p.y]!='#'&&p.x>=0&&p.y>=0&&p.x<n&&p.y<m&&vis[p.x][p.y]==0)            {                vis[p.x][p.y]=1;                if(i==0) strcat(p.c,"N");                if(i==1) strcat(p.c,"S");                if(i==2) strcat(p.c,"W");                if(i==3) strcat(p.c,"E");                Q.push(p);            }        }    }}int main(){    int i,j;    while(cin>>n>>m)    {        memset(vis,0,sizeof(vis));        for(i=0;i<n;i++)            for(j=0;j<m;j++)            {                cin>>map[i][j];                if(map[i][j]=='S')                sx=i, sy=j;            }        flag=0;        bfs(sx,sy);        if(flag==0)        printf("Can't eat it!/n");    }    return 0;}
TOJ 3973 Maze Again
描述
The maze is the same as problem D, and I strongly recommend you solve the previous one first because it.s easier than this.
This time, we want you design the command for our poor robot to move from where it is to its destination. The command sequence.s length should be the shortest. If several solutions exist, find the lexicographically minimum one.
Lexicographical sequence is the order in one dictionary. For example, “cat” is less than “do”, and “do” is less than “dog”.
輸入
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with one integer N (1 <= N <= 50), indicating the size of the maze. The followed N lines are N strings whose length is also N, indicating the maze.
輸出
For each case, output a command string if there is a solution, otherwise output -1.
樣例輸入
22S.#T4S#...#T..##.....
樣例輸出
RDDDDRRRUUL
題目意思和貪吃蛇差不多，但是這題要注意DLRU要按字典序，所以一開始的dir要寫好。
#include <cstring>#include <iostream>#include <queue>#include <cstdio>using namespace std;int n,dir[4][2]= {1,0,0,-1,0,1,-1,0};//字典序int vis[51][51],ex,ey,sx,sy,flag;char map[51][51];struct node{    int x;    int y;    char c[101];};void bfs(int x,int y){    node a,p,b;    int i;    vis[x][y]=1;    a.x=x;    a.y=y;    memset(a.c,'/0',sizeof(a.c));    queue<node>Q;    Q.push(a);    while(!Q.empty())    {        b=Q.front();        Q.pop();        if(map[b.x][b.y]=='T')        {            flag=1;            printf("%s/n",b.c);            return;        }        for(i=0;i<4;i++)        {            p=b;            p.x=p.x+dir[i][0];            p.y=p.y+dir[i][1];            if(map[p.x][p.y]!='#'&&p.x>=0&&p.y>=0&&p.x<n&&p.y<n&&vis[p.x][p.y]==0)            {                vis[p.x][p.y]=1;                if(i==0) strcat(p.c,"D");                if(i==1) strcat(p.c,"L");                if(i==2) strcat(p.c,"R");                if(i==3) strcat(p.c,"U");                Q.push(p);            }        }    }}int main(){    int i,j,o;    cin>>o;    while(o--)    {		cin>>n;        memset(vis,0,sizeof(vis));        for(i=0;i<n;i++)            for(j=0;j<n;j++)            {                cin>>map[i][j];                if(map[i][j]=='S')                sx=i,sy=j;            }        flag=0;        bfs(sx,sy);        if(flag==0)        printf("-1/n");    }    return 0;}