Codeforces Good Bye 2017 B (BF算法也就是枚举法的一种)

浏览: 50 发布日期: 2018-01-01 分类: c

题目:B. New Year and Buggy Bot
Bob programmed a robot to navigate through a 2d maze.
The maze has some obstacles. Empty cells are denoted by the character '.', where obstacles are denoted by '#'.
There is a single robot in the maze. It's start position is denoted with the character 'S'. This position has no obstacle in it. There is also a single exit in the maze. It's position is denoted with the character 'E'. This position has no obstacle in it.
The robot can only move up, left, right, or down.
When Bob programmed the robot, he wrote down a string of digits consisting of the digits 0 to 3, inclusive. He intended for each digit to correspond to a distinct direction, and the robot would follow the directions in order to reach the exit. Unfortunately, he forgot to actually assign the directions to digits.
The robot will choose some random mapping of digits to distinct directions. The robot will map distinct digits to distinct directions. The robot will then follow the instructions according to the given string in order and chosen mapping. If an instruction would lead the robot to go off the edge of the maze or hit an obstacle, the robot will crash and break down. If the robot reaches the exit at any point, then the robot will stop following any further instructions.
Bob is having trouble debugging his robot, so he would like to determine the number of mappings of digits to directions that would lead the robot to the exit.
Input
The first line of input will contain two integers n and m (2 ≤ n, m ≤ 50), denoting the dimensions of the maze.
The next n lines will contain exactly m characters each, denoting the maze.
Each character of the maze will be '.', '#', 'S', or 'E'.
There will be exactly one 'S' and exactly one 'E' in the maze.
The last line will contain a single string s (1 ≤ |s| ≤ 100) — the instructions given to the robot. Each character of s is a digit from 0 to 3.
Output
Print a single integer, the number of mappings of digits to directions that will lead the robot to the exit.

样例:
Examples
Input
5 6
.....#
S....#
.#....
.#....
...E..
333300012
Output
1
Input
6 6
......
......
..SE..
......
......
......
01232123212302123021
Output
14
Input
5 3
...
.S.
###
.E.
...
3
Output
0

提示:For the first sample, the only valid mapping is , where D is down, L is left, U is up, R is right;

题意:有一个地图,其中S表示机器人开始的位置,E表示机器人结束的位置,#表示障碍,‘.’表示空的地方,本来0123分别表示上下左右,但是现在不知道哪一个数字表示上,哪一个数表示下等。。。;
之后第一行输入两个数表示输入地图的行和列,然后输入地图,再之后输入一串字符,即0123,。然后让你判断这段字符能否在所有不同表示情况下能走出来的次数(这里的不同表示情况就是上下左右可能为0123,也可能为1230,也可能为1320,等);

思路:将所有上下左右被0123组合表示的情况列出来然后用一个数组存下来,然后再输入的字符串中的0123的字符表示其下标,其内部的0123分别表示上下左右;然后移动S,然后判断能否顺利到达E;

新技巧:就是在数的组合情况很多的时候,但是是已知多少的时候,若需要将每一种组合都进行一遍的话,则就可以把这些数提前存到数组中;(和前面写的那些字符串的枚举法一个道理);

代码:

#include<stdio.h>
int mu[24][4]={{0,1,2,3},{0,1,3,2},{0,2,3,1},{0,2,1,3},{0,3,2,1},{0,3,1,2},{1,0,2,3},{1,0,3,2},{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},{2,0,1,3},{2,0,3,1},{2,1,3,0},{2,1,0,3},{2,3,0,1},{2,3,1,0},{3,0,1,2},{3,0,2,1},{3,1,2,0},{3,1,0,2},{3,2,1,0},{3,2,0,1}};
int main()
{
    char s[55][55],a[105];
    int n,m,i,j,b[2][2],p,q,num;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%s",s[i]);
    scanf("%s",a);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            if(s[i][j]=='S')
            {b[0][0]=i;b[0][1]=j;}
            if(s[i][j]=='E')
            {b[1][0]=i;b[1][1]=j;}
        }
    num=0;
    for(i=0;i<24;i++)
    {
        p=b[0][0];q=b[0][1];
        for(j=0;a[j]!='\0';j++)
        {
            switch(mu[i][a[j]-'0'])
            {
                case 0:p--;break;
                case 1:q--;break;
                case 2:p++;break;
                case 3:q++;break;
            }
            if(s[p][q]=='#')
                break;
            else if(p<0||q<0||p>=n||q>=m)
                break;
            else if(s[p][q]=='E')
            {
                num++;break;
            }
        }
    }
    printf("%d\n",num);
    return 0;
}
返回顶部