| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:我的coding超时,我用的STL的queue,哪位能帮我看看哪里可以提高, 感激不尽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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator