2766.cpp

ACM北京赛区比赛的试题源码,在PKU在线评测可以通过.

#include <iostream.h>
#include <string.h>
//#include <fstream.h>

//ofstream fout;
//ifstream fin;

int a[52][52];
int n,r,t;
char v[51][4];
int pos[51][2];
char out[51][4];

struct Tdest{
	int rt;
	int dt;
};

Tdest d[51][4];//这次的bug在这里!! 因为,没有足够的空间,所以导致修改了其他参数,而且极难检查出来!!
//开始时,是d[50][4].测试很多组都没问题,然后找到了原题,原数据,一组组测试终于发现有些输出不了,然后
//逐渐单步,才发现这个问题 郁闷....

void GetD()
{
	int i,x,y;
	for(i=1;i<=r;i++) 
	{
		x = pos[i][0];
		y = pos[i][1];
		x--;
		while (x>0 && !a[x][y]) x--;
		if (!x) 
		{
			d[i][0].rt = 0;
			d[i][0].dt = y;
			out[i][0] = 1;
		}
		else 
		{
			d[i][0].rt = a[x][y];
			d[i][0].dt = 1;
		} //0
		x = pos[i][0];
		y = pos[i][1];
		y++;
		while (y<n+1 && !a[x][y]) y++;
		if (y == n+1) 
		{
			d[i][1].rt = x;
			d[i][1].dt = n+1;
			out[i][1] = 1;
		}
		else 
		{
			d[i][1].rt = a[x][y];
			d[i][1].dt = 2;
		} //1
		x = pos[i][0];
		y = pos[i][1];
		x++;
		while (x<n+1 && !a[x][y]) x++;
		if (x == n+1) 
		{
			d[i][2].rt = n+1;
			d[i][2].dt = y;
			out[i][2] = 1;
		}
		else 
		{
			d[i][2].rt = a[x][y];
			d[i][2].dt = 3;
		} //2
		x = pos[i][0];
		y = pos[i][1];
		y--;
		while (y>0 && !a[x][y]) y--;
		if (!y) 
		{
			d[i][3].rt = x;
			d[i][3].dt = 0;
			out[i][3] = 1;
		}
		else 
		{
			d[i][3].rt = a[x][y];// 这里是开始的小bug,写成了d[i][0]
			d[i][3].dt = 0;//
		} //3
	}//for
}
int startr,startd;
void Solve()
{
	int nr,nd,t;
	nr = startr;
	nd = startd;
	while (!out[nr][nd] && !v[nr][nd])
	{
		v[nr][nd] = 1;
		t = nr;
		nr = d[nr][nd].rt;
		nd = d[t][nd].dt;
	}
	if (v[nr][nd]) 
	{
		cout<<0<<" "<<0<<endl;
		return ;
	}
	cout<<d[nr][nd].rt<<" "<<d[nr][nd].dt<<endl;
}

int main()
{
	int i,T;
	int lrx,lry;
//	fout.open("outupt.txt");
	cin>>T;
	while (T--)
	{
		memset(a,0,sizeof a);
		memset(v,0,sizeof v);
		memset(out,0,sizeof out);
		cin>>n>>r;
		for(i=1;i<=r;i++) 
		{
			cin>>pos[i][0]>>pos[i][1];
			a[pos[i][0]][pos[i][1]] = i;
		}
		cin>>lrx>>lry;
		GetD();
		if (lrx == 0) 
		{
			lrx++;
			while (lrx<n+1 && !a[lrx][lry]) lrx++;
			if (lrx == n+1) 
			{
				cout<<n+1<<" "<<lry<<endl;
				continue;
			} else 
			{
				startr = a[lrx][lry];
				startd = 3;
				Solve();
				continue;
			}
		}
		if (lrx == n+1)
		{
			lrx--;
			while (lrx>0 && !a[lrx][lry]) lrx--;
			if (!lrx)
			{
				cout<<0<<" "<<lry<<endl;
				continue;
			} else 
			{
				startr = a[lrx][lry];
				startd = 1;
				Solve();
				continue;
			}
		}
		if (lry == n+1)
		{
			lry--;
			while (lry>0 && !a[lrx][lry]) lry--;
			if (!lry)
			{
				cout<<lrx<<" "<<0<<endl;
				continue;
			} else 
			{
				startr = a[lrx][lry];
				startd = 0;
				Solve();
				continue;
			}
		}
		if (!lry)
		{
			lry++;
			while (lry<n+1 && !a[lrx][lry]) lry++;
			if (lry == n+1)
			{
				cout<<lrx<<" "<<n+1<<endl;
				continue;
			} else 
			{
				startr = a[lrx][lry];
				startd = 2;
				Solve();
				continue;
			}
		}
	}
	return 0;
}