Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

G++1A ,C++WA ,为什么

Posted by tjrac6016203284 at 2018-05-28 21:09:10 on Problem 3083
#include<iostream>
#include<string.h>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
int rotp[4]= {3,0,1,2};
char graph[50][50];
int step[50][50],Ans;
int n,m;
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};

struct node
{
    int x,y;
};
node S,temp,temp_1,E;

void BFS()
{
    queue<node>Q;
    step[S.x][S.y]=0;
    Q.push(S);
    while(!Q.empty())
    {
        temp=Q.front();
        Q.pop();
        for(int i=0;i<4;++i)
        {
            temp_1.x=temp.x+dx[i];
            temp_1.y=temp.y+dy[i];
            if(temp_1.x>=0&&temp_1.x<n&&temp_1.x>=0&&temp_1.y<m&&graph[temp_1.x][temp_1.y]!='#'&&(step[temp_1.x][temp_1.y]==-1||step[temp_1.x][temp_1.y]>step[temp.x][temp.y]+1))
            {
                step[temp_1.x][temp_1.y]=step[temp.x][temp.y]+1;
                Q.push(temp_1);
            }
        }
    }
}



struct Ant
{
    int x,y;
    int step;
    int dx[4];
    int dy[4];
    int jud()
    {
        for(int i=0; i<4; ++i)
        {
            int temp_x=x+dx[i];
            int temp_y=y+dy[i];
            if(temp_x>=0&&temp_x<n&&temp_y>=0&&temp_y<m&&graph[temp_x][temp_y]!='#')
                return i;
        }
        return -1;
    }
    void take(int ctor)
    {
        int temp_dx[4];
        int temp_dy[4];
        for(int i=0; i<4; ++i)
        {
            temp_dx[i]=dx[(i+ctor)%4];
            temp_dy[i]=dy[(i+ctor)%4];
        }
        for(int i=0; i<4; ++i)
        {
            dx[i]=temp_dx[i];
            dy[i]=temp_dy[i];
        }
    }
};

int main()
{
    Ant left_ant,right_ant;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(step,-1,sizeof(step));
        Ans=0;
        scanf("%d%d",&m,&n);
        for(int i=0; i<n; ++i)
        {
            getchar();
            for(int j=0; j<m; ++j)
            {
                scanf("%c",&graph[i][j]);
            }
        }
        for(int i=0; i<n; ++i) //找到S起始点
        {
            for(int j=0; j<m; ++j)
            {
                if(graph[i][j]=='S')
                {
                    left_ant.x=right_ant.x=i;
                    left_ant.y=right_ant.y=j;
                    left_ant.step=0;
                    right_ant.step=0;
                    S.x=i;
                    S.y=j;
                }
                if(graph[i][j]=='E')
                {
                    E.x=i;
                    E.y=j;
                }
            }
        }
        left_ant.dx[0]=0,left_ant.dx[1]=-1,left_ant.dx[2]=0,left_ant.dx[3]=1;
        left_ant.dy[0]=-1,left_ant.dy[1]=0,left_ant.dy[2]=1,left_ant.dy[3]=0;
        right_ant.dx[0]=0,right_ant.dx[1]=-1,right_ant.dx[2]=0,right_ant.dx[3]=1;
        right_ant.dy[0]=1,right_ant.dy[1]=0,right_ant.dy[2]=-1,right_ant.dy[3]=0;

        do
        {

            int i=left_ant.jud();
           // printf("(%d,%d)-->%d\n",left_ant.x,left_ant.y,i);
            if(i==-1)
                break;
            left_ant.x=left_ant.x+left_ant.dx[i];
            left_ant.y=left_ant.y+left_ant.dy[i];
            left_ant.take(rotp[i]);
            ++left_ant.step;
        }
        while(graph[left_ant.x][left_ant.y]!='E');

        do
        {

            int i=right_ant.jud();
           // printf("(%d,%d)-->%d\n",right_ant.x,right_ant.y,i);
            if(i==-1)
                break;
            right_ant.x=right_ant.x+right_ant.dx[i];
            right_ant.y=right_ant.y+right_ant.dy[i];
            right_ant.take(rotp[i]);
            ++right_ant.step;
        }
        while(graph[right_ant.x][right_ant.y]!='E');
        BFS();


        if(step[E.x][E.y]!=-1)
            Ans=step[E.x][E.y]+1;


        printf("%d %d %d\n",left_ant.step+1,right_ant.step+1,Ans);


    }
    return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator