遭遇战_模拟

发布于 2019-05-21  11 次阅读


题目大意

在一个n*n的矩形内,给出两个人的开始位置和开始方向,规定每一个人不可以走过自己走过的路径,每走一步的时间为1,且自己遇到障碍时右转,而对手向左转,转弯不用消耗时间,求在什么位置,两人可以相遇


思路

看数据的范围感觉bfs刚好不会炸,然后想想这题和广搜好像并没有什么很大的关系,所以就直接模拟解决就可以了
每一个时间每一个人个向前走一步,判断一下就可以了
特别要注意开始就在一起的情况


#include 
#include 
#include 
using namespace std;
#define maxn 1001
#define fill(x,y) memset(x,y,sizeof(x))
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
inline int read()
{
    int x=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
    return x;
}
int f[maxn][maxn],f1[maxn][maxn];
int main()
{
    freopen("fight.in","r",stdin);
    freopen("fight.out","w",stdout);
    int t=read();
    for (int o=1;o<=t;o++)
    {
        fill(f,0);fill(f1,0);
        int n=read();
        int x=read(),y=read(),z=read();
        x++; y++;
        int x1=read(),y1=read(),z1=read();
        x1++; y1++;
        if (x==x1&&y==y1)
        {
            printf("%d %d",x-1,y-1);
            continue;
        }
        int tx=dx[z],ty=dy[z];
        int tx1=dx[z1],ty1=dy[z1];
        f[x][y]=1; f1[x1][y1]=1;
        int fl=2,ans=0,fll=0,flll=0,xx=0;
        while (fl>0)
        {
            ans++;
            if (x+tx>0&&x+tx<=n&&y+ty>=1&&y+ty<=n&&f[x+tx][y+ty]==0&&fll==0)
            {
                f[x+tx][y+ty]=1;
                x+=tx; y+=ty;
            }
            else if (fll==0)
            {
                if (z<3)
                    z++;
                else z=0;
                tx=dx[z]; ty=dy[z];
                if (x+tx==0||x+tx==n+1||y+ty==0||y+ty==n+1||f[x+tx][y+ty]==1)
                {
                    fl--;
                    fll=1;
                }
                else 
                {
                    f[x+tx][y+ty]=1;
                    x+=tx; y+=ty;
                }
            }
            if (x1+tx1>0&&x1+tx1<=n&&y1+ty1>=1&&y1+ty1<=n&&f1[x1+tx1][y1+ty1]==0&&flll==0)
            {
                f1[x1+tx1][y1+ty1]=1;
                x1+=tx1; y1+=ty1;
            }
            else if (flll==0)
            {
                if (z1>0)
                    z1--;
                else z1=3;
                tx1=dx[z1]; ty1=dy[z1];
                if (x1+tx1==0||x1+tx1==n+1||y1+ty1==0||y1+ty1==n+1||f1[x1+tx1][y1+ty1]==1)
                {
                    fl--;
                    flll=1;
                }
                else 
                {
                    f1[x1+tx1][y1+ty1]=1;
                    x1+=tx1; y1+=ty1;
                }
            }
            if (x==x1&&y==y1)
            {
                printf("%d %d\n",x-1,y-1);
                xx=1;
                break;
            }
        }
        if (xx==0) printf("-1\n");
    }
}   
]]>