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

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

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

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

TOJ 3128 簡單版貪吃蛇

描述

現在我們來簡化蛇的身體，假設初始化的時候蛇的身體只有一個頭而已（呵，當然是假設的），那么蛇去吃食物的時候就不必考慮碰到自己的身體了。例：

5 5.....S....###.#E....#####
那么從S到E最短的走法是EEESSWWW。說明：N（north），S（south），W（west），E（east）。如果吃不到食物就輸出Can't eat it!注意：路徑是最短的走的。
輸入
輸入數據有多組，每組輸入的第一行是兩個正整數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;}