3083.cpp

来自「pku acm上的3083源代码」· C++ 代码 · 共 74 行

#include<iostream>
using namespace std;
struct point{
    int x;
    int y;
};
char G[41][41];
bool find = false;
point start;
int w, h ,num;
//第三维为人所朝的方向 
int move[4][4][2]={{{-1,0},{0,1},{1,0},{0,-1}},{{0,1},{1,0},{0,-1},{-1,0}},{{1,0},{0,-1},{-1,0},{0,1}},{{0,-1},{-1,0},{0,1},{1,0}}};

void DFS_Visit(point now, int face)
{
    int i, x, y;
    point k;
    for(i=0; i<=3; i++)
    {
        x = now.x+move[face][i][0];
        y = now.y+move[face][i][1];
        if(G[x][y] == 'E')
        {
            //find = true;
            break;
        }
        if(x>=1 && y>=1 && x<=w && y<=h && G[x][y] == '.')
        {
            num++;
            k.x = x;
            k.y = y;
            DFS_Visit(k, i);
        }
    }
}

void DFS(int face)
{
    DFS_Visit(start, face);
}


int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int cases, i, j, k, face;
    scanf("%d",&cases);
    for(i=1; i<=cases; i++)
    {
        scanf("%d%d",&w, &h);
        for(j=1; j<=h; j++)
        {
            for(k=1; k<=w; k++)
                scanf("%c", &G[j][k]);
            if(G[j][k] == 'S')
            {
                start.x = k;
                start.y = j;
                if(j == 1)
                    face = 0;
                else if(j == h)
                    face = 2;
                else if(k == 1)
                    face = 1;
                else if(k == w)
                    face = 3;
            }
        }
        DFS(face);
    } 
    return 0;
}