The Donkey of Hrbust

There are several test cases.
In each test case:
First line is an integer N, meaning that the forest is a N×N grid.
The second line contains three integers R, C and D, meaning that the donkey is in the cell (R,C) when they started running, and it's original direction is D. D can be 0, 1, 2 or 3. 0 means east, 1 means south , 2 means west, and 3 means north.
The third line has the same format and meaning as the second line, but it is for the tiger.
The input ends with N = 0. ( 2 <= N <= 1000, 0 <= R, C < N)

C++14(g++5.4) 解法, 执行用时: 12ms, 内存消耗: 2272K, 提交时间: 2020-08-04 18:05:57

#include<iostream>
#include<string.h>
using namespace std;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int x1,y1,d1,x2,y2,d2,n;
bool vis1[1010][1010];
bool vis2[1010][1010];
int main()
{
    while(1)
    {
        cin>>n;
        if (!n) break;
        cin>>y1>>x1>>d1;
        cin>>y2>>x2>>d2;
        memset(vis1,false,sizeof(vis1));
        memset(vis2,false,sizeof(vis2));
        vis1[x1][y1]=1;
        vis2[x2][y2]=1;
        bool f1=1,f2=1,f=0;
        while (f1||f2)
        {
        if (f1)
        if (y1+dy[d1]<n&&y1+dy[d1]>=0&&x1+dx[d1]<n&&x1+dx[d1]>=0&&vis1[x1+dx[d1]][y1+dy[d1]]==0)
            {x1=x1+dx[d1];y1=y1+dy[d1];vis1[x1][y1]=1;}
        else {
                int d=(d1+1)%4;
                if (y1+dy[d]<n&&y1+dy[d]>=0&&x1+dx[d]<n&&x1+dx[d]>=0&&vis1[x1+dx[d]][y1+dy[d]]==0)
                {d1=d;x1=x1+dx[d1];y1=y1+dy[d1];vis1[x1][y1]=1;}
                else f1=0;
             }
        if (f2)
        if (y2+dy[d2]<n&&y2+dy[d2]>=0&&x2+dx[d2]<n&&x2+dx[d2]>=0&&vis2[x2+dx[d2]][y2+dy[d2]]==0)
            {x2=x2+dx[d2];y2=y2+dy[d2];vis2[x2][y2]=1;}
        else {
                int d=(d2+3)%4;
                if (y2+dy[d]<n&&y2+dy[d]>=0&&x2+dx[d]<n&&x2+dx[d]>=0&&vis2[x2+dx[d]][y2+dy[d]]==0)
                {d2=d;x2=x2+dx[d2];y2=y2+dy[d2];vis2[x2][y2]=1;}
                else f2=0;
             }
        if (x1==x2&&y1==y2)
        {cout<<y1<<" "<<x1<<endl;f=1;break;}
        }
    if(!f) cout<<-1<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 44ms, 内存消耗: 8284K, 提交时间: 2018-04-24 21:24:07

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010],b[1010][1010],F,F1,F2,fx[4]={0,1,0,-1},fy[4]={1,0,-1,0},n;
void dfs(int x,int y,int d,int xx,int yy,int dd)
{
	if(x==xx&&y==yy)
	{
		F=1;
		printf("%d %d\n",x,y);
		return;
	}
	if(!F1&&!F2)
	{
		F=1;
		printf("-1\n");
		return;
	}
	a[x][y]=b[xx][yy]=1;
	if(F1&&x+fx[d]>=0&&x+fx[d]<n&&y+fy[d]>=0&&y+fy[d]<n&&!a[x+fx[d]][y+fy[d]])
		x+=fx[d],y+=fy[d];
	else if(F1)
	{
		d=(d+1)%4;
		x+=fx[d];
		y+=fy[d];
		if(x<0||x>=n||y<0||y>=n||a[x][y])
		{
			F1=0;
			x-=fx[d];
			y-=fy[d];
		}
	}
	if(F2&&xx+fx[dd]>=0&&xx+fx[dd]<n&&yy+fy[dd]>=0&&yy+fy[dd]<n&&!b[xx+fx[dd]][yy+fy[dd]])
		xx+=fx[dd],yy+=fy[dd];
	else if(F2)
	{
		dd=(dd+3)%4;
		xx+=fx[dd];
		yy+=fy[dd];
		if(xx<0||xx>=n||yy<0||yy>=n||b[xx][yy])
		{
			F2=0;
			xx-=fx[dd];
			yy-=fy[dd];
		}
	}
	dfs(x,y,d,xx,yy,dd);
	if(F)
		return;
}
int main()
{
	int x,y,d,xx,yy,dd;
	while(~scanf("%d",&n)&&n)
	{
		scanf("%d%d%d%d%d%d",&x,&y,&d,&xx,&yy,&dd);
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		F=0;
		F1=F2=1;
		dfs(x,y,d,xx,yy,dd);
	}
	return 0;
}

详情