这个思路是哪里不对嘛...

P1649 [USACO07OCT] Obstacle Course S

Chino @ 2018-06-09 15:53:10

只有10分 想不明白.. 写的有点蠢 求大佬看看qwq

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int read()
{
    char ch = getchar();
    int f = 1;
    int x = 0;
    while(ch < '0' || ch > '9'){if(ch == '-')f = 0;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return f?x:x*-1;
}
struct node
{
    int x,y,a,count;
};
int main()
{
    int n = read();
    int visited[101][101] = {};
    char ss[100][220] = {};
    char s[100][101] = {};
    int dx[4] = {-1,0,0,1};
    int dy[4] = {0,-1,1,0};

    getchar();
    for(int i = 0;i < n;i ++)
    {
        gets(ss[i]);
    }

    int len = strlen(ss[0]);

    for(int i = 0;i < len;i ++)
    {
        for(int j = 0,k = 0;j < len;j ++)
        {
            if(ss[i][j] != ' ')
            {
                s[i][k ++] = ss[i][j];
            }
        }
    }

    int x1,y1,x2,y2;
    for(int i = 0;i < n;i ++)
    {
        for(int j = 0;j < n;j ++)
        {
            if(s[i][j] == 'A')
            {
                x1 = i,y1 = j;
            }
            if(s[i][j] == 'B')
            {
                x2 = i,y2 = j;
            }
        }
    }  
    queue<node> q;
    node a = {x1,y1,-1,0};
    q.push(a);
    visited[x1][y1] = 1;
    int min = 99999999;
    while(q.size())
    {
        node t = q.front();
        q.pop();

        if(t.x == x2 && t.y == y2)
        {
            if(min > t.count)
            {
                min = t.count;
                break;
            }
        }

        for(int i = 0;i < 4;i ++)
        {
            int nx = dx[i] + t.x;
            int ny = dy[i] + t.y;

            if(nx >= 0 && nx < n && ny >= 0 && ny < n && s[nx][ny] != 'x' && visited[nx][ny] == 0)
            {
                visited[nx][ny] = 1;
                node x = {nx,ny,t.a,t.count};

                if(t.a == -1)
                {
                    if(nx - t.x == 1)
                    {
                        x.a = 1;
                    }
                    if(t.x - nx == 1)
                    {
                        x.a = 2;
                    }
                    if(ny - t.y == 1)
                    {
                        x.a = 3;
                    }
                    if(t.y - ny == 1)
                    {
                        x.a = 4;
                    }
                }
                else
                {
                    int tx = nx - t.x;
                    int ty = ny - t.y;

                    if(x.a == 1 && tx != 1)
                    {
                        if(tx == -1)
                        {
                            x.a = 2;
                        }
                        if(ty == 1)
                        {
                            x.a = 3;
                        }
                        if(ty == -1)
                        {
                            x.a = 4;
                        }
                        x.count ++;
                    }
                    if(x.a == 2 && tx != -1)
                    {
                        if(tx == 1)
                        {
                            x.a = 1;
                        }
                        if(ty == 1)
                        {
                            x.a = 3;
                        }
                        if(ty == -1)
                        {
                            x.a = 4;
                        }
                        x.count ++;
                    }
                    if(x.a == 3 && ty != 1)
                    {
                        if(tx == 1)
                        {
                            x.a = 1;
                        }
                        if(tx == -1)
                        {
                            x.a = 2;
                        }
                        if(ty == -1)
                        {
                            x.a = 4;
                        }
                        x.count ++;
                    }
                    if(x.a == 4 && ty != -1)
                    {
                        if(tx == 1)
                        {
                            x.a = 1;
                        }
                        if(tx == -1)
                        {
                            x.a = 2;
                        }
                        if(tx == 1)
                        {
                            x.a = 3;
                        }
                        x.count ++;
                    }
                }
                q.push(x); 
            }
        }
    }
    if(min == 99999999)
    {
        printf("-1");
    }
    else
    {
        printf("%d",min);
    }
    return 0;
}

by Steinway @ 2018-06-09 15:55:43

你把空格也读进去了吧(空格也可以走 如果你这样写)


by Chino @ 2018-06-09 16:01:05

@Steinway 已经处理掉了呀


by Steinway @ 2018-06-09 16:04:36

@Chino 那稍等 我帮你改改


by Chino @ 2018-06-09 16:13:36

@Steinway 感谢dalao


by Steinway @ 2018-06-09 16:20:03

@Chino 题意是开始的方向随意,你应该是那里错了吧


by Chino @ 2018-06-09 16:22:04

@Steinway 没错呀.. 我一开始设置的方向为-1 然后广搜的一开始加了个判断 如果是-1的话就不会增加次数 然后定下4个开始的方向


by Rikka @ 2018-06-09 16:25:05

@Chino 嗯. 对的 你加我qq吧 我改完发给你


by Steinway @ 2018-06-09 16:25:57

@Chino 尴尬..拿了别人的号来说 你加我Q吧 我改完发给你 17678925


|