当前位置: 代码迷 >> C语言 >> 帮忙排排错
  详细解决方案

帮忙排排错

热度:433   发布时间:2008-04-06 19:34:08.0
帮忙排排错
昨天参加学校的编程比赛,有几道题怎么也通过不了,大家帮忙看下是什么问题
搜索更多相关的解决方案: 编程  学校  

----------------解决方案--------------------------------------------------------
/////////////////////////////////////////////////////////////////////
/*
Given a string of uppercase letters, is it possible to erase one or
more characters to get the string 'BUAA'?
输入
The first line contains a single integer T(1<=T<=15), the number of
test cases.
Each test case is a single line containing at least 1 and at most
100 uppercase letters.
There are no spaces, TABs, lowercase letters or other characters
before, or after the string.
输出
For each test case, print the case number and 'Yes' if it is possible
to get 'BUAA', or 'No' otherwise.
The output is case-sensitive, so don't output 'YES' or 'yes' when
'Yes' should be output.
样例输入
4
ACMBUAA
ACMAAUB
HELLOWORLD
BUACMA
样例输出
Case 1: Yes
Case 2: No
Case 3: No
Case 4: Yes
*/
/////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
void WorkOut(char word[], char buaa[]);
int main()
{
    int i, n;
    char word[200];
    char buaa[5] = "BUAA";

    cin >> n;

    for (i = 0; i < n; i++)
    {
        cin >> word;
        cout << "Case " << i + 1;
        WorkOut(word, buaa);
    }
    return 0;
}

void WorkOut(char *word, char *buaa)
{
    int i = 0, j = 0;
    bool find = false;
    while (word[i] != '\0')
    {
        if (word[i] == buaa[j])
        {
            j++;
            i++;
        }
        else
            i++;

        if (buaa[j] == '\0')
        {
            cout << ": Yes " << endl;
            find = true;
            break;
        }
    }

    if (!find)
        cout << ": No " << endl;
}
////////////////////////////////////////////////////////////////////////
/*
给的测试项都行,但是也许有什么情况没考虑到,帮忙想一下吧
*/
//////////////////////////////////////////////////////////////////////

[[it] 本帖最后由 andyzhshg 于 2008-4-6 19:35 编辑 [/it]]
----------------解决方案--------------------------------------------------------
////////////////////////////////////////////////////////////////////
/*
有一些机器人在屋子里行走,他们要在不相互碰撞的情况下完成指令,地图是矩形的,每个机器人占据一个格子的位置,我们知道机器人的初始位置和方向,以及一系列命令,命令是有序的,不会有两个命令是同时发生的。
输入

多组数据,第一行为数据的组数k

每组数据以两个整数n,m开始,表示地图的尺寸,n为W-E走向的尺寸,m为N-S走
向的尺寸 (n,m<=100)

接下来一行为两个整数为p,q (p,q<=100) , 表示p个机器人,q个命令

接下来p行描述机器人的初始信息,位置(x,y)
(1<=x<=n,1<=y<=m) ,和一个字母表示机器人初始面对的方向('N','S','E','W')

接下来q行描述指令,指令构成如下
<robot i><action><repeat>

表示机器人,动作种类,重复次数

action种类有3种

   1. 'L':左转90度
   2. 'R':右转90度
   3. 'F':前进一个格子

重复次数不会大于100。

机器人一旦发生碰撞,则停止运行,并输出相关的错误信息。
输出

有3种:

如果第i个机器人(x=0或者y=0或者x=n+1或者y=m+1),输出 Robot i crashes
into the wall

如果i和j相撞,i是移动的那个机器人,输出 Robot i crashes into robot j

如果没有碰撞发生,输出 OK
样例输入
2
5 4
2 2
1 1 E
5 4 W
1 F 7
2 F 7
5 4
2 2
1 1 E
5 4 W
1 L 96
1 F 2
样例输出
Robot 1 crashes into the wall
OK
*/
//////////////////////////////////////////////////////////////////////

#include <iostream>
using namespace std;

struct robot
{
    int x;
    int y;
    int direction;
};

struct Move
{
    int num;
    int turn;
    int repeat;
};

int maze[102][102];
robot rbt[101];
Move move[100];

void WorkOut(int m, int n, int p, int q)
{
    int i, j, s, t;

    for (s = 0; s < q; s++)
    {
        for (t = 0; t < move[s].repeat; t++)
        {
            if (move[s].turn == 0)
            {
                switch(rbt[move[s].num].direction)
                {
                    case 0:
                        i = rbt[move[s].num].x;
                        j = rbt[move[s].num].y - 1;
                        break;
                    case 1:
                        i = rbt[move[s].num].x + 1;
                        j = rbt[move[s].num].y;
                        break;
                    case 2:
                        i = rbt[move[s].num].x;
                        j = rbt[move[s].num].y + 1;
                        break;
                    case 3:
                        i = rbt[move[s].num].x - 1;
                        j = rbt[move[s].num].y;
                        break;
                }

                if (maze[j][i] == -1)
                {
                    cout << "Robot " << move[s].num << " crashes into the wall" << endl;
                    return;
                }
                else if(maze[j][i] == 0)
                {
                    maze[j][i] = move[s].num;
                    maze[rbt[move[s].num].y][rbt[move[s].num].x] = 0;
                    rbt[move[s].num].y = j;
                    rbt[move[s].num].x = i;
                }
                else
                {
                    cout << "Robot " << move[s].num << " crashes into robot "  << maze[j][i] << endl;
                    return;
                }
            }

            else if (move[s].turn == 1)
            {
                if (rbt[move[s].num].direction == 3)
                    rbt[move[s].num].direction = 0;
                else
                    rbt[move[s].num].direction += 1;
            }

            else
            {
                if (rbt[move[s].num].direction == 0)
                    rbt[move[s].num].direction = 3;
                else
                    rbt[move[s].num].direction -= 1;
            }
        }
    }

    cout << "OK" << endl;
}

int main()
{
    int k;
    int m, n, p, q;
    int i, j, s, t;
    char dir;

    cin >> k;

    for (i = 0; i < k; i++)
    {
        cin >> n >> m >> p >> q;

        for (s = 0; s <= m + 1; s++)//初始化地图
        {
            maze[s][0] = -1;
            maze[s][n+1] = -1;
        }
        for (s = 1; s <= n; s++)
        {
            maze[0][s] = -1;
            maze[m+1][s] = -1;
            for (t = 1; t <= m; t++)
                maze[t][s] = 0;
        }

        for (j = 1; j <= p; j++)//初始化地图和机器人位值
        {
            cin >> rbt[j].x >> rbt[j].y;
            maze[rbt[j].y][rbt[j].x] = j;

            cin >> dir;
            switch(dir)
            {
                case 'N':
                    rbt[j].direction = 0;
                    break;
                case 'E':
                    rbt[j].direction = 1;
                    break;
                case 'S':
                    rbt[j].direction = 2;
                    break;
                case 'W':
                    rbt[j].direction = 3;
                    break;
            }
        }

        for (j = 0; j < q; j++)
        {
            cin >> move[j].num;

            cin >> dir;
            switch(dir)
            {
                case 'L':
                    move[j].turn = -1;
                    break;
                case 'R':
                    move[j].turn = 1;
                    break;
                case 'F':
                    move[j].turn = 0;
                    break;
            }

            cin >> move[j].repeat;
        }

        WorkOut(m, n, p, q);
    }

    return 0;
}
/////////////////////////////////////////////////////////////////////////////////////
/*
可以通过样例,但是提交时有错误。
*/
///////////////////////////////////////////////////////////////////////////////////

[[it] 本帖最后由 andyzhshg 于 2008-4-6 19:40 编辑 [/it]]
----------------解决方案--------------------------------------------------------
第一题很搞笑



----------------解决方案--------------------------------------------------------
第一题貌似很容易
复杂度为O(N)
----------------解决方案--------------------------------------------------------
回复 4# 的帖子
是啊,要是道难题通过不了就算了,这么简单的题……
还是帮忙看下有什么问题吧
题目详见:
http://acm.buaa.edu.cn/oj/problems.php?c=30

[[it] 本帖最后由 andyzhshg 于 2008-4-6 20:09 编辑 [/it]]
----------------解决方案--------------------------------------------------------
第二题纯模拟,在重复次数那里可以通过优化减少时间
----------------解决方案--------------------------------------------------------
嗯,但是错误不在于超时,而是答案错误
----------------解决方案--------------------------------------------------------
我做个提交试试
----------------解决方案--------------------------------------------------------
你提交不了的,需要校内的帐号,你贴这里我提交一下吧
----------------解决方案--------------------------------------------------------
  相关解决方案