Source

Problem Id:1103  User Id:kingway 
Memory:-552K  Time:0MS
Language:C++  Result:Time Limit Exceed

Source 

#include <stdio.h>
#include <iostream.h>

int i, j, len, longest, w, h, dir, num, dir1;
int a[75][75], b[75][75];

int I(int i, int dir);
int J(int j, int dir);
int Search(int i1, int j1);
int main()
{
	int n, dir2;
	char ch;
	for (n=1; 1; n++)
	{
		cin>>w>>h;
		if (w==0 && h==0)
			break;
		for (i=0; i<h; i++)
		{
			for (j=0; j<w; j++)
			{
				cin>>ch;
				a[i][j] = ch=='/' ? 5:3;
				b[i][j] = 0;
			}
		}
		num = 0;
		longest = 0;
		for (i=0; i<h; i++)
		{
			for (dir=1, j=0; j<w; j+=w-1, dir=3)
			{
				if (b[i][j]!=2)
				{
					len = 0;
					if (b[i][j]==0)
						dir2 = dir;
					else
					{
						if (a[i][j]==3)
							dir2 = b[i][j];
						else
							dir2 = b[i][j]==1 ? 3:1;
					}
					if (dir2 == dir)
					{
						dir1 = dir;
					//	cout<<"\nstart: "<<i<<" * "<<j<<"  "<<dir<<endl;
						Search(i, j);
					}
				}
			}
		}
		for (j=0; j<w; j++)
		{
			for (dir=2, i=0; i<h; i+=h-1, dir=4)
			{
				if (b[i][j]!=2)
				{
					len = 0;
					if (b[i][j]==0)
						dir2 = dir;
					else
					{
						if (a[i][j]==3)
							dir2 = b[i][j];
						else
							dir2 = b[i][j]==1 ? 3:1;
					}
					if (dir == dir2)
					{
						dir1 = dir;
					//	cout<<"\nstart: "<<i<<" & "<<j<<"  "<<dir<<endl;
						Search(i, j);
					}
				}
			}
		}
		for (i=0; i<h; i++)
		{
			for (j=0; j<w; j++)
			{
				if (b[i][j]!=2)
				{
					len = 0;
					if (a[i][j]==3)
						dir = b[i][j];
					else
						dir = b[i][j]==1 ? 3:1;
					dir1 = dir;
				//	cout<<"\nstart: "<<i<<" ^ "<<j<<"  "<<dir<<endl;
					Search(i, j);
				}
			}
		}
		cout<<"Maze #"<<n<<":\n";
		if (num!=0)
		{
			cout<<num;
			if (num == 1)
				cout<<" Cycle;";
			else
				cout<<" Cycles;";
			cout<<" the longest has length "<<longest<<".\n";
		}
		else
			cout<<"There are no cycles.\n";
	}
	return 0;
}

int I(int i, int dir)
{
        switch (dir)
        {
                case 2: i++; break;
                case 4: i--; break;
        }
        return i;
}

int J(int j, int dir)
{
        switch (dir)
        {
                case 1: j++; break;
                case 3: j--; break;
        }
        return j;
}

int Search(int i1, int j1)
{
	while (i1>=0 && i1<h && j1>=0 && j1<w)
	{
		if (a[i1][j1]==3)
		{
			if (b[i1][j1]==0)
				b[i1][j1] = (dir ==1 || dir == 4) ? 3:1;
			else
				b[i1][j1] = 2;
			dir = (dir + 4) >= 7 ? (7 - dir):(3 - dir);
			i1 = I(i1, dir);
			j1 = J(j1, dir);
		}
		else
		{
			if (b[i1][j1]==0)
				b[i1][j1] = (dir == 1 || dir == 2) ? 1:3;
			else
				b[i1][j1] = 2;
			dir = 5 - dir;
			i1 = I(i1, dir);
			j1 = J(j1, dir);
		}
	//	cout<<i1<<" "<<j1<<" "<<dir<<endl;
		len++;
		if (i1==i && j1==j && dir1 == dir)
		{
			num++;
		//	cout<<"cycle"<<endl;
			if (longest < len)
				longest = len;
			return 1;
		}
	}
//	cout<<"not cycle"<<endl;
	return 0;
}

• Re:>>奇怪！！Memory有负值为-552k，Time为0ms，返回结果且为Time Limit Exceed. (3424) rcrt10 2009-07-25 21:57:11
  • Re:>>奇怪！！Memory有负值为-552k，Time为0ms，返回结果且为Time Limit Exceed. (6) rcrt10 2009-07-25 21:57:34