posts - 3,  comments - 1,  trackbacks - 0
这题没把我弄疯了.一个小时写完,改了2个小时...题目给的数据太弱了,需要自己写一些数据来验证...在这里给大家提供些数据

题目
Maze
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 1205 Accepted: 399

Description

Acm, a treasure-explorer, is exploring again. This time he is in a special maze, in which there are some doors (at most 5 doors, represented by 'A', 'B', 'C', 'D', 'E' respectively). In order to find the treasure, Acm may need to open doors. However, to open a door he needs to find all the door's keys (at least one) in the maze first. For example, if there are 3 keys of Door A, to open the door he should find all the 3 keys first (that's three 'a's which denote the keys of 'A' in the maze). Now make a program to tell Acm whether he can find the treasure or not. Notice that Acm can only go up, down, left and right in the maze.

Input

The input consists of multiple test cases. The first line of each test case contains two integers M and N (1 < N, M < 20), which denote the size of the maze. The next M lines give the maze layout, with each line containing N characters. A character is one of the following: 'X' (a block of wall, which the explorer cannot enter), '.' (an empty block), 'S' (the start point of Acm), 'G' (the position of treasure), 'A', 'B', 'C', 'D', 'E' (the doors), 'a', 'b', 'c', 'd', 'e' (the keys of the doors). The input is terminated with two 0's. This test case should not be processed.

Output

For each test case, in one line output "YES" if Acm can find the treasure, or "NO" otherwise.

Sample Input

4 4
S.X.
a.X.
..XG
....
3 4
S.Xa
.aXB
b.AG
0 0

Sample Output

YES
NO
 
数据:
5 5
S....
XXAXa
GX..X
.X...
.....

20 20
S..................a
aXXXXXXXXXXAXXXXXXX.
.X........bb......X.
.XbXXXXXXXXXXXXXX.X.
.X.X.....c......X.X.
aXbX.XXXXXXXXXX.X.X.
.X.X.X........X.X.X.
.X.X.X.XDXXXX.X.X.X.
.X.X.X.X..XXX.X.X.X.
.X.X.X.X.XG.X.X.X.X.
.X.XcX.X.XXEX.CeX.X.
.X.X.X.X.e..X.X.X.X.
.X.X.X.XXXXXX.X.X.X.
.X.X.X........X.X.X.
.X.X.XXXXXXXXXX.X.X.
.X.X..c.........X.X.
.X.XXXXXXXBXXXXXX.X.
.X........b.......X.
.XXXXXXXXXXXXXXXXXX.
.d..e...a........a..
主要思想,先找钥匙..搜索一遍,得到能找到的钥匙,然后开门.把能开的门都打开..打开门之后再找钥匙,然后在开门.
直到找到G..
 
代码如下:

Source Code

Problem: 2157 User: luoguangyao
Memory: 276K Time: 0MS
Language: C++ Result: Accepted
  • Source Code
      1#include <iostream>
      2
      3using namespace std;
      4
      5int m;
      6int n;
      7char map[22][22];
      8int allkey[6= {0};
      9int key[6= {0};
     10int mark[22][22= {0};
     11int mark2[22][22= {0};
     12int markkey[22][22= {0};
     13int lock = 1;
     14int kk = 0;
     15
     16void FindKey(int x,int y)
     17{
     18    if ((map[x][y] >= 'a'&& map[x][y] <= 'e')
     19            && markkey[x][y] != 1)
     20    {
     21        key[map[x][y] - 'a']++;
     22
     23        markkey[x][y] = 1;
     24    }

     25
     26    mark2[x][y] = 1;
     27
     28    if (mark2[x + 1][y] != 1 && x + 1 < m && map[x + 1][y] != 'X' && map[x + 1][y] != 'A' && map[x + 1][y] != 'B' 
     29        && map[x + 1][y] != 'C' && map[x + 1][y] != 'D' && map[x + 1][y] != 'E')
     30    {
     31        FindKey(x + 1 , y);
     32    }

     33
     34    if (mark2[x - 1][y] != 1 && x - 1 >= 0 && map[x - 1][y] != 'X' && map[x - 1][y] != 'A' && map[x - 1][y] != 'B'
     35        && map[x - 1][y] != 'C' && map[x - 1][y] != 'D' && map[x - 1][y] != 'E')
     36    {
     37        FindKey(x - 1 , y);
     38    }

     39
     40    if (mark2[x][y + 1!= 1 && y + 1 < n && map[x][y + 1!= 'X'  && map[x][y + 1!= 'A' && map[x][y + 1!= 'B'
     41        && map[x][y + 1!= 'C' && map[x][y + 1!= 'D' && map[x][y + 1!= 'E' )
     42    {
     43        FindKey(x , y + 1);
     44    }

     45
     46    if (mark2[x][y - 1!= 1 && y - 1 >= 0 && map[x][y - 1!= 'X'  && map[x][y - 1!= 'A' && map[x][y - 1!= 'B' 
     47        && map[x][y - 1!= 'C' && map[x][y - 1!= 'D' && map[x][y - 1!= 'E')
     48    {
     49        FindKey(x , y - 1);
     50    }

     51}

     52
     53void Findroute(int x,int y)
     54{
     55    if (map[x][y] == 'G')
     56    {
     57        lock = 0;
     58    }

     59
     60    FindKey(x , y);
     61
     62    mark[x][y] = 1;
     63
     64    if (mark[x + 1][y] != 1 && x + 1 < m && map[x + 1][y] != 'X')
     65    {
     66        if (map[x + 1][y] >= 'A' && map[x + 1][y] <= 'E')
     67        {
     68            if (key[map[x + 1][y] - 'A'!= 0 && allkey[map[x + 1][y] - 'A'== key[map[x + 1][y] - 'A'])
     69            {
     70                Findroute(x + 1 , y);
     71            }

     72        }

     73        else
     74        {
     75            Findroute(x + 1 , y);
     76        }

     77    }

     78
     79    if (mark[x - 1][y] != 1 && x - 1 >= 0 && map[x - 1][y] != 'X')
     80    {
     81        if (map[x - 1][y] >= 'A' && map[x - 1][y] <= 'E')
     82        {
     83            if (key[map[x - 1][y] - 'A'!= 0 && key[map[x - 1][y] - 'A'== allkey[map[x - 1][y] - 'A'])
     84            {
     85                Findroute(x - 1 , y);
     86            }

     87        }

     88        else
     89        {
     90            Findroute(x - 1 , y);
     91        }

     92    }

     93
     94    if (mark[x][y - 1!= 1 && y - 1 >= 0 && map[x][y - 1!= 'X')
     95    {
     96        if (map[x][y - 1>= 'A' && map[x][y - 1<= 'E')
     97        {
     98            if (key[map[x][y - 1- 'A'!= 0 && allkey[map[x][y - 1- 'A'== key[map[x][y - 1- 'A'])
     99            {
    100                Findroute(x , y - 1);
    101            }

    102        }

    103        else
    104        {
    105            Findroute(x , y - 1);
    106        }

    107    }

    108
    109    if (mark[x][y + 1!= 1 && y + 1 < n && map[x][y + 1!= 'X')
    110    {
    111        if (map[x][y + 1>= 'A' && map[x][y + 1<= 'E')
    112        {
    113            if (key[map[x][y + 1- 'A'!= 0 && allkey[map[x][y + 1- 'A'== key[map[x][y + 1- 'A'])
    114            {
    115                Findroute(x , y + 1);
    116            }

    117        }

    118        else
    119        {
    120            Findroute(x , y + 1);
    121        }

    122    }

    123
    124}

    125
    126int main()
    127{
    128    int i;
    129    int j;
    130
    131    while (cin >> m >> n)
    132    {
    133        int px = -1;
    134        int py = -1;
    135        int gx = -1;
    136        int gy = -1;
    137
    138        memset(key,0,sizeof(key));
    139        memset(allkey,0,sizeof(allkey));
    140        memset(map,'\0',sizeof(map));
    141        memset(mark,0,sizeof(mark));
    142        memset(mark2,0,sizeof(mark2));
    143        memset(markkey,0,sizeof(markkey));
    144        lock = 1;
    145
    146        if (m == 0 && n == 0)
    147        {
    148            break;
    149        }

    150
    151        for (i = 0; i < m ; ++i)
    152        {
    153            for (j = 0; j < n; ++j)
    154            {
    155                cin >> map[i][j];
    156
    157                if (map[i][j] >= 'a' && map[i][j] <= 'e')
    158                {
    159                    allkey[map[i][j] - 'a']++;
    160                }

    161
    162                if (map[i][j] == 'S')
    163                {
    164                    px = i;
    165                    py = j;
    166                }

    167
    168                if (map[i][j] == 'G')
    169                {
    170                    gx = i;
    171                    gy = j;
    172                }

    173            }

    174        }

    175
    176        if (px == -1 || py == -1 || gx == -1 || gy == -1)
    177        {
    178            cout << "NO" << endl;
    179            continue;
    180        }

    181
    182        Findroute(px,py);
    183
    184        if (lock == 1)
    185        {
    186            cout << "NO" << endl;
    187        }

    188        else
    189        {
    190            cout << "YES" << endl;
    191        }

    192    }

    193
    194    return 0;
    195}

    196
posted on 2009-03-07 15:14 生活要低调 阅读(1143) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(1)

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜