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