X星的坦克戰(zhàn)車很奇怪，它必須交替地穿越正能量輻射區(qū)和負(fù)能量輻射區(qū)才能保持正常運(yùn)轉(zhuǎn)，否則將報廢。 某坦克需要從A區(qū)到B區(qū)去（A，B區(qū)本身是安全區(qū)，沒有正能量或負(fù)能量特征），怎樣走才能路徑最短？ 已知的地圖是一個方陣，上面用字母標(biāo)出了A，B區(qū)，其它區(qū)都標(biāo)了正號或負(fù)號分別表示正負(fù)能量輻射區(qū)。 例如： A + - + - - + - - + - + + + - + - + - + B + - + - 坦克車只能水平或垂直方向上移動到相鄰的區(qū)。 數(shù)據(jù)格式要求： 輸入第一行是一個整數(shù)n，表示方陣的大小， 4<=n<100 接下來是n行，每行有n個數(shù)據(jù)，可能是A，B，+，-中的某一個，中間用空格分開。 A，B都只出現(xiàn)一次。 要求輸出一個整數(shù)，表示坦克從A區(qū)到B區(qū)的最少移動步數(shù)。 如果沒有方案，則輸出-1 例如： 用戶輸入： 5 A + - + - - + - - + - + + + - + - + - + B + - + - 則程序應(yīng)該輸出： 10 資源約定： 峰值內(nèi)存消耗 < 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;}新聞熱點(diǎn)
疑難解答
