An Easy PRoblem Of BFS Problem links: http://codevs.cn/problem/1215/ It takes me about one hour to solve it because of my unfamiliar to BFS. I have never used c++ to solve problems, so I write this program to remember me about the grammer of queue.
emptyTest whether container is emptysizeReturn sizefrontaccess next elementbackAccess last elementpushInsert element emplace Construct and insert element (???)popRemove next elementswap Swap contents (may be used between two queues)This is my code
#include <iostream>#include <queue>using namespace std;int main(){ int t; cin >> t; for (int k = 0; k < t; k++) { int n; bool r = 0; char c; int a[20][20] = { 0 }; queue <int> qx, qy; cin >> n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { cin >> c; if (c == 's') { qx.push(i); qy.push(j); a[i][j] = 0; // 0 means wall, and 1 means load } else if (c == 'e') a[i][j] = 2; else if (c == '#') a[i][j] = 0; else if (c == '.') a[i][j] = 1; } int x, y; while (!qx.empty()) { x = qx.front(); y = qy.front(); if (a[x + 1][y] == 1) { qx.push(x + 1); qy.push(y); a[x + 1][y] = 0; } else if (a[x + 1][y] == 2) { cout << "YES" << endl; r = 1; break; } if (a[x - 1][y] == 1) { qx.push(x - 1); qy.push(y); a[x - 1][y] = 0; } else if (a[x - 1][y] == 2) { cout << "YES" << endl; r = 1; break; } if (a[x][y + 1] == 1) { qx.push(x); qy.push(y + 1); a[x][y + 1] = 0; } else if (a[x][y + 1] == 2) { cout << "YES" << endl; r = 1; break; } if (a[x][y - 1] == 1) { qx.push(x); qy.push(y - 1); a[x][y - 1] = 0; } else if (a[x][y - 1] == 2) { cout << "YES" << endl; r = 1; break; } qx.pop(); qy.pop(); } if (r == 0) cout << "NO" << endl; } return 0;}新闻热点
疑难解答
