X星的坦克戰車很奇怪，它必須交替地穿越正能量輻射區和負能量輻射區才能保持正常運轉，否則將報廢。 某坦克需要從A區到B區去（A，B區本身是安全區，沒有正能量或負能量特征），怎樣走才能路徑最短？ 已知的地圖是一個方陣，上面用字母標出了A，B區，其它區都標了正號或負號分別表示正負能量輻射區。 例如： A + - + - - + - - + - + + + - + - + - + B + - + - 坦克車只能水平或垂直方向上移動到相鄰的區。 數據格式要求： 輸入第一行是一個整數n，表示方陣的大小， 4<=n<100 接下來是n行，每行有n個數據，可能是A，B，+，-中的某一個，中間用空格分開。 A，B都只出現一次。 要求輸出一個整數，表示坦克從A區到B區的最少移動步數。 如果沒有方案，則輸出-1 例如： 用戶輸入： 5 A + - + - - + - - + - + + + - + - + - + B + - + - 則程序應該輸出： 10 資源約定： 峰值內存消耗 < 512M CPU消耗 < 1000ms
簡單BFS.
#include <bits/stdc++.h>using namespace std;vector< vector<char> > g;vector< vector<bool> > b;int n;const int dx[] = {1, 0, -1, 0};const int dy[] = {0, 1, 0, -1};struct Node{ int x, y, step;};bool exist(int x, int y){ return x >= 0 && x < n && y >= 0 && y < n;}int main(){ //freopen("in", "r", stdin); scanf("%d/n", &n); string s; g.resize(n); for (int i = 0; i < n; i++) { getline(cin, s); for (int j = 0; j < s.size(); j++) { if (s[j] != ' ') g[i].push_back(s[j]); } } Node A, B; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][j] == 'A') A.x = i, A.y = j, A.step = 0; } } b.resize(n); for (int i = 0; i < n; i++) b[i].resize(n); queue<Node> q; q.push(A); b[A.x][A.y] = true; while (!q.empty()) { Node node = q.front(); q.pop(); b[node.x][node.y] = true; for (int i = 0; i < 4; i++) { int xx = node.x + dx[i], yy = node.y + dy[i]; if (exist(xx, yy)) { if (b[xx][yy]) continue; if (g[xx][yy] == 'B') { cout << node.step + 1 << endl; return 0; } if (g[xx][yy] != g[node.x][node.y]) { q.push((Node){xx, yy, node.step + 1}); } } } } cout << "-1" << endl;}新聞熱點
疑難解答
