首页 > 代码库 > sicily 1215 脱离地牢
sicily 1215 脱离地牢
做Sicily 1215脱离地牢 这一题,一直Restrict function,都快崩溃了。
最后发现是内存泄露,就是new出来的东西没有及时delete导致的。
具体是在广度优先搜索的时候,每找一次邻居就new出一些节点,有些节点已被visited了然后我直接忽略它们,实际上是得把它们delete掉的,还有就是pop出一个节点后,在处理完邻居之后要把这个节点delete了
贴个代码片段:
第32,35行便是要注意的地方。
运行效率:0秒,312KB
完整代码如下:
// Problem#: 1215 // Submission#: 2642938 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ // All Copyright reserved by Informatic Lab of Sun Yat-sen University #include<iostream> #include<stdio.h> #include<queue> #include<cstring> #include<vector> #include<algorithm> #include<cmath> using namespace std; char **prison; bool *visited; unsigned char *dotPerLine = NULL; unsigned char **oneLineDot = NULL; int n, m; char dirParis[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; char dirHelen[4][2]; int dotCount; struct Node { int px; int py; int hx; int hy; int step; Node() { step = 0; parent = NULL; } Node* parent; }; int hashPoint(int x, int y) { int p=0; p+=dotPerLine[x-1]; // for(int j = 0; j < y; j++) // { // if(prison[x][j] == '.' || prison[x][j] == 'H' || prison[x][j] == 'P') // p++; // } // p+=oneLineDot[x][y-1]; return p; } int hashNode(Node* node) { return hashPoint(node->hx-1,node->hy-1)*dotCount+hashPoint(node->px-1,node->py-1); } //bool cmp(const Node* a, const Node* b) //{ // int disA = abs(a->px-a->hx) +abs(a->py-a->hy); // int disB = abs(b->px-b->hx) +abs(b->py-b->hy); // return disA < disB; //} vector<Node*> getAdj(Node* node) { vector<Node*> ret; for(int i = 0; i < 4; i++) { char pNext = prison[node->px-1+dirParis[i][0]][node->py-1+dirParis[i][1]]; char hNext = prison[node->hx-1+dirHelen[i][0]][node->hy-1+dirHelen[i][1]]; if(pNext != '#' && pNext != '!') { if(hNext != '!') { Node* newNode = new Node; newNode->px = node->px+dirParis[i][0]; newNode->py = node->py+dirParis[i][1]; if(hNext == '#') { newNode->hx = node->hx; newNode->hy = node->hy; } else { newNode->hx = node->hx+dirHelen[i][0]; newNode->hy = node->hy+dirHelen[i][1]; } newNode->step = node->step+1; ret.push_back(newNode); newNode->parent = node; } } } return ret; } bool isPass(Node* node) { return node->px == node->hx && node->py == node->hy || node->px == node->parent->hx && node->py == node->parent->hy && node->hx == node->parent->px && node->hy == node->parent->py; } int bfs(Node* node) { queue<Node*> Q; Q.push(node); while(!Q.empty()) { Node* node = Q.front(); Q.pop(); vector<Node*> adj = getAdj(node); //sort(adj.begin(),adj.end(),cmp); for(int i = 0; i < adj.size(); i++) { Node* child = adj.at(i); if(child->step > 255) return -1; int index = hashNode(child); if(!visited[index]) { visited[index] = true; if(!isPass(child)) { Q.push(child); } else { return child->step; } } else { delete child; } } delete node; } return -1; } int main() { while(cin >> n >> m) { dotPerLine = new unsigned char[n]; memset(dotPerLine,0,n); oneLineDot = new unsigned char*[n]; prison = new char*[n]; for(int i = 0; i < n; i++) { prison[i] = new char[m]; cin >> prison[i]; } for(int i = 0; i < n; i++) { oneLineDot[i] = new unsigned char[m]; memset(oneLineDot[i],0,m); } char d[4]; cin >> d; for(int i = 0; i < 4; i++) { switch(d[i]) { case'N': dirHelen[i][0] = -1; dirHelen[i][1] = 0; break; case'S': dirHelen[i][0] = 1; dirHelen[i][1] = 0; break; case'W': dirHelen[i][0] = 0; dirHelen[i][1] = -1; break; case'E': dirHelen[i][0] = 0; dirHelen[i][1] = 1; break; } } //find initial position Node* init = new Node; dotCount = 0; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { if(prison[i][j] == '.') { oneLineDot[i][j] = 1; dotCount++; dotPerLine[i]++; } else if(prison[i][j] == 'H') { init->hx = i+1; init->hy = j+1; oneLineDot[i][j] = 1; dotCount++; dotPerLine[i]++; } else if(prison[i][j] == 'P') { init->px = i+1; init->py = j+1; oneLineDot[i][j] = 1; dotCount++; dotPerLine[i]++; } } for(int i = 1; i < n-1; i++) { dotPerLine[i] += dotPerLine[i-1]; for(int j = 2; j < m-1; j++) { oneLineDot[i][j] += oneLineDot[i][j-1]; } } int count = dotCount*dotCount; visited = new bool[count]; memset(visited,0,count); visited[hashNode(init)] = true; int result = bfs(init); if(result == -1) cout << "Impossible" << endl; else cout << result << endl; for(int i = 0; i < n; i++) { delete [] prison[i]; delete [] oneLineDot[i]; } delete [] prison; delete [] dotPerLine; delete [] oneLineDot; delete [] visited; } }
sicily 1215 脱离地牢
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。