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

Re:我的coding超时,我用的STL的queue,哪位能帮我看看哪里可以提高, 感激不尽

Posted by _plxer at 2020-07-10 20:58:35 on Problem 3322
In Reply To:我的coding超时,我用的STL的queue,哪位能帮我看看哪里可以提高, 感激不尽 Posted by:yangzefeng at 2012-07-04 13:53:57
> #include<iostream>
> #include<queue>
> #define MAX 550
> using namespace std;
> 
> struct node
> {
> 	int r, c, method, d, step;//method 0表示站着,1表示躺着
> };
> struct Node
> {
> 	int method, d;
> 	bool vis;
> }vis[MAX][MAX];
> char map[MAX][MAX];
> int R, C, sr, sc, tr, tc, minStep;
> int dir[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};//上下右左
> queue<node> qq;
> 
> bool inmap(int r, int c)
> {
> 	return (r >= 0 && r < R && c >= 0 && c < C && map[r][c] != '#');
> }
> 
> int bfs()
> {
> 	int i, j, k, newMethod, newd;
> 	node now, tmp;
> 	while(!qq.empty())
> 	{
> 		now = qq.front();
> 		qq.pop();
> 		for(k = 0; k < 4; k++)
> 		{
> 			//判断状态
> 			if(now.method == 0)
> 			{
> 				newMethod = 1;
> 				newd = k;
> 				i = now.r + dir[k][0];
> 				j = now.c + dir[k][1];
> 			}
> 			else
> 			{
> 				if(now.d == k)
> 				{
> 					newMethod = 0;
> 					newd = -1;
> 					i = now.r + 2 * dir[k][0];
> 					j = now.c + 2 * dir[k][1];
> 				}
> 				else if( (now.d == 1 && k == 0) || (now.d == 0 && k == 1) || (now.d == 2 && k == 3) || (now.d == 3 && k == 2) )
> 				{
> 					newMethod = 0;
> 					newd = -1;
> 					i = now.r + dir[k][0];
> 					j = now.c + dir[k][1];
> 				}
> 				else
> 				{
> 					newMethod = now.method;
> 					newd = now.d;
> 					i = now.r + dir[k][0];
> 					j = now.c + dir[k][1];
> 				}
> 			}
> 			if(!inmap(i, j) || (vis[i][j].vis && vis[i][j].method == newMethod && vis[i][j].d == newd) || (newMethod == 0 && map[i][j] == 'E') || (newMethod == 1 && map[i + dir[newd][0]][j + dir[newd][1]] == '#'))
> 				continue;
> 			tmp.r = i;
> 			tmp.c = j;
> 			tmp.method = newMethod;
> 			tmp.d = newd;
> 			tmp.step = now.step + 1;
> 			vis[i][j].vis = true; vis[i][j].method = newMethod; vis[i][j].d = newd;
> 			if(tmp.r == tr && tmp.c == tc && tmp.method == 0)
> 			{
> 				if(minStep > tmp.step)
> 					minStep = tmp.step;
> 				return minStep;
> 			}
> 			qq.push(tmp);
> 		}
> 	}
> 	return -1;
> }
> 
> int main()
> {
> 	int i, j, flag, firstMethod, firstd, firstdr, firstdc;
> 	bool first;
> 	while(scanf("%d %d", &R, &C) == 2)
> 	{
> 		if(R == 0 && C == 0)
> 			break;
> 		first = true;
> 		minStep = 999999;
> 		firstMethod = 0;
> 		firstd = -1;
> 		memset(vis, NULL, sizeof(vis));
> 		for(i = 0; i < R; i++)
> 		{
> 			scanf("%s", &map[i]);
> 			for(j = 0; j < C; j++)
> 			{
> 				if(map[i][j] == 'X')
> 				{
> 					if(first)
> 					{
> 						sr = i;
> 						sc = j;
> 						first = false;
> 					}
> 					else
> 					{
> 						firstMethod = 1;
> 						firstdr = i - sr;
> 						firstdc = j - sc;
> 						if(firstdr == -1 && firstdc == 0)
> 							firstd = 0;
> 						else if(firstdr == 1 && firstdc == 0)
> 							firstd = 1;
> 						else if(firstdr = 0 && firstdc == 1)
> 							firstd = 2;
> 						else
> 							firstd = 3;
> 					}
> 				}
> 				else if(map[i][j] == 'O')
> 				{
> 					tr = i;
> 					tc = j;
> 				}
> 			}
> 		}
> 		while(!qq.empty())
> 			qq.pop();
> 		node first;
> 		first.r = sr;
> 		first.c = sc;
> 		first.method = firstMethod;
> 		first.step = 0;
> 		first.d = firstd;//-1表示站着
> 		vis[sr][sc].vis = true; vis[sr][sc].method = firstMethod; vis[sr][sc].d = firstd;
> 		qq.push(first);
> 		flag = bfs();
> 		if(flag == -1)
> 			printf("Impossible\n");
> 		else
> 			printf("%d\n", flag);
> 	}
> 	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