POJ 1573 Robot Motion（模拟、DFS、BFS）

题目链接：http://poj.org/problem?id=1573

分析：

这道题既可以模拟出结果，也可以用DFS或者BFS搜索。

模拟：

// 模拟
// #include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
using namespace std;

char G[10+7][10+7];
int vis[10+7][10+7];

int main()
{
    int n, m, s;
    while(scanf("%d %d %d", &n, &m, &s), n+m+s)
    {
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<n; i++)
            scanf("%s", G[i]);
        // for(int i=0; i<n; i++)
        //     printf("%s\n", G[i]);
        int sx = 0, sy = s-1;
        int step1 = 0, step2 = 0;
        int flag = 0;
        while(1)
        {
            if(G[sx][sy] == 'N')
                vis[sx][sy] = 1, sx--;
            else if(G[sx][sy] == 'E')
                vis[sx][sy] = 1, sy++;
            else if(G[sx][sy] == 'S')
                vis[sx][sy] = 1, sx++;
            else if(G[sx][sy] == 'W')
                vis[sx][sy] = 1, sy--;
            step1 ++;   // 记录走了几步
            
            if(sx < 0 || sy < 0 || sx >= n || sy >= m)  // 判断是否走出方格
            {
                flag = 1;
                break;
            }
            else if(vis[sx][sy] == 1)   // 判断是否陷入循环，并标记
            {
                vis[sx][sy] = 2;
                flag = 2;
                break;
            }
        }
        if(flag == 2)   // 如果进入了循环
        { // 把循环部分再走一遍并记录循环过程中走了几步，其实可以用个二维数组记录一下每个点是第几步走到的，这样就可以不用再走一遍循环部分
            while(1)    
            {
                 if(G[sx][sy] == 'N')
                    sx--;
                else if(G[sx][sy] == 'E')
                    sy++;
                else if(G[sx][sy] == 'S')
                    sx++;
                else if(G[sx][sy] == 'W')
                    sy--;
                
                step2 ++;
                if(vis[sx][sy] == 2)    // 如过走到了循环起点，就结束
                    break;
            } 
        }
        if(flag == 1)
        {
            // if(step1 > 1)
                printf("%d step(s) to exit\n", step1);
            // else
                // printf("%d step to exit\n", step1);
        }
        else if(flag == 2)
        {
            // if(step1 > 1)
                printf("%d step(s) before a loop of %d step(s)\n", step1 - step2, step2);
            // else
                // printf("%d step before a loop of %d step(s)\n", step1 - step2, step2);
        }
    }




    return 0;
}

DFS:

// 递归写法
// DFS
#include <cstdio>
#include <cstring>
using namespace std;

char G[20][20];
int step[20][20];
int n, m, s;
int exitStep;
int loopStep;
int sx, sy;
bool loop = false;

void dfs(int row, int col, int num)
{
    if(row < 0 || col < 0 || row >= n || col >= m)  // 走出方格条件
    {
        exitStep = num;
        return ;
    }

    if(step[row][col])  // 有走回到了原来走过的点，说明是一个循环
    {
        loop = true;
        loopStep = num - step[row][col];    // 循环步数
        sx = row;
        sy = col;
        return;
    }

    step[row][col] = num;   // 起点不能标记为0，因为我们以非零标记此点是否走过
    if(G[row][col] == 'N')
        dfs(row-1, col, num+1);
    else if(G[row][col] == 'E')
        dfs(row, col+1, num+1);
    else if(G[row][col] == 'S')
        dfs(row+1, col, num+1);
    else if(G[row][col] == 'W')
        dfs(row, col-1, num+1);
}

int main()
{
   
    while(scanf("%d %d %d", &n, &m, &s), n+m+s)
    {
        memset(step, 0, sizeof(step));
        for(int i=0; i<n; i++)
        {
            scanf("%s", G[i]);
        }

        loop = false;
        dfs(0, s-1, 1);
        // for(int i=0; i<n; i++)
        // {
        //     for(int j=0; j<m; j++)
        //         printf("%d", step[i][j]);
        //     printf("\n");
        // }
        if(loop)
            printf("%d step(s) before a loop of %d step(s)\n", step[sx][sy] - 1, loopStep);
        else
        {
            printf("%d step(s) to exit\n", exitStep -1);
        }
        
    }


    return 0;
}

BFS:

// BFS
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct node{
    int x, y;
    node(int xx=0, int yy=0) : x(xx), y(yy) {}  // 构造函数
};

char G[20][20];
int step[20][20];
int n, m , s;
int numstep;    // 记录走了多少步
bool loop = false;  // 记录是否有循环
int loopstep;
int loopx, loopy;   // 循环起点

void bfs()
{
    queue<node> q;
    q.push(node(0, s-1));   // 起点放入队列中
    while(!q.empty())
    {
        node e = q.front();
        q.pop();
        

        if(step[e.x][e.y])  // 如果已经走过了， 说明陷入循环
        {
            loop = true;
            loopx = e.x;
            loopy = e.y;
            loopstep = numstep - step[e.x][e.y];
            break;
        }

        numstep ++;
        step[e.x][e.y] = numstep;   // 标记当前点已经走过，而且是第几步走到这里的

        if(G[e.x][e.y] == 'N')
            e.x -= 1;
        else if(G[e.x][e.y] == 'E')
            e.y += 1;
        else if(G[e.x][e.y] == 'S')
            e.x += 1;
        else if(G[e.x][e.y] == 'W')
            e.y -= 1;
        
        if(e.x >=0 && e.y >= 0 && e.x < n && e.y < m)
                q.push(e);
        else            // 出了方格就退出
            break;
        
    }
}

int main()
{
    while(scanf("%d %d %d", &n, &m, &s), n+m+s)
    {
        for(int i=0; i<n; i++)
            scanf("%s", G[i]);
        memset(step, 0, sizeof(step));
        loop = false;
        numstep = 0;
        bfs();

        if(loop)
            printf("%d step(s) before a loop of %d step(s)\n", step[loopx][loopy]-1, loopstep+1);
        else
        {
            printf("%d step(s) to exit\n", numstep);
        }
    }


    return 0;
}