同題：UVa 00825 – Walking on the Safe Side
在正方城這個城市走路是件相當容易的事，因為所有的道路都是像棋盤的線一樣，把城市切割成一塊一塊的正方形。大部分的十字路口都是安全的，行人可以直接通過。然而也有少數的十字路口比較危險，所以建有地下道或天橋供行人通過。
現在有一個人想要從位於城市西北方 (也就是左上角) 的公園十字路口到位於東南方 (也就是右下角) 的車站十字路口去。由於他是個懶惰的人，他不想要走比需要多 一點點的路，也就是說他一定是往下或往右走，絕對不會往上或往左走。另外，他也不喜歡走天橋或地下道，所以他會避開這些危險的十字路口。你的任務就是幫他算一下從左上角走到右下角有多少種不同的走法。
以下的圖顯示出有 4 條東西向的道路，有 5 條南北向的道路，有 3 個十字路口是危險的。所以從左上角走到右下角要走 (N-1)+(W-1) = 3 + 4 = 7 格的距離，並且總共有 4 種不同的走法。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 輸入的第一列有一個正整數，代表以下有多少組測試資料。 每組測試資料的第一列有 2 個整數 W 和 N (均不大於 100），W 代表東西向道路的數目，N 代表南北向道路的數目，編號如上圖所示。 接下來的 W 列代表這 W 條東西向道路，每列的第一個數為這是第幾條東西向道路，接下來有 0 個或多個不等的數，代表某些南北向道路與這條東西向道路相交的十字路口是危險的。 輸入的第一列與第一組測試資料之間，以及各組測試資料之間均有一空白列，第一組Sample Input 表示的路如上圖所示，請參考。 | 每組測試資料輸出一列，為一個整數。代表這個人從左上角走到右下角有多少種不同的走法。測試資料間亦請空一列。 |
| 2 4 5 1 2 2 3 3 5 4 5 5 1 2 1 2 3 4 3 1 2 3 4 1 2 3 5 5 1 2 3 | 4 0 |
解題思路
會有「起點或終點是危險十字路口」的情況，這種時候答案就是 0。
存取危險十字路口座標時可以把座標點轉換成 0-Base 的座標，這樣子方便走 BFS 的時後比較好判斷。可以使用字串的方式 getline 危險十字路口，並用 For迴圈 將裡面的數字獨立出來存到一個陣列中。需要注意測資中不會按照順序給這些座標，有可能會先給第二行再來是第一行，所以存座標的時候需要使用那一行的第一個數字。
使用 BFS，每次往下或是往右走，並宣告一個二維陣列，裡面的資料預設為 0。跑 BFS 時如果可以往下或往右走，則將下一個點位置的二維陣列值 += 目前位置的二維陣列值。需要注意的是，在存取下一次 BFS 起點的時候不能重複將同一個起點存放到陣列中，所以可以宣告一個 Map 來確認目前要存的起點是否已經被存過了。
答案就是二維陣列中最左下角的那個資料。
範例程式碼－ZeroJudge D198: Walking on the Safe Side
#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<pair<int, int>, int>MAP;
vector<vector<long long int>>step;
int N, M;
pair<int, int> axis (const int a, const int b) {
pair<int, int>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
void BFS(vector<pair<int, int>>start) {
if (start.size() == 0) return;
vector<pair<int, int>>newStart;
map<pair<int, int>, int>appear;
for (int i = 0; i<start.size(); i++) {
int y = start[i].first, x = start[i].second;
if (y == N-1 && x == M-1) return;
if (y + 1 < N && MAP[axis(y+1, x)] == 0) {
step[y+1][x] += step[y][x];
if (appear[axis(y+1, x)] == 0) newStart.push_back(axis(y+1, x));
appear[axis(y+1, x)]++;
}
if (x + 1 < M && MAP[axis(y, x+1)] == 0) {
step[y][x+1] += step[y][x];
if (appear[axis(y, x+1)] == 0) newStart.push_back(axis(y, x+1));
appear[axis(y, x+1)]++;
}
}
BFS(newStart);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int i = 0; i<T; i++) {
MAP.clear();
step.clear();
cin >> N >> M;
string s;
getline(cin, s);
for (int j = 0; j<N; j++) {
string str, tmp;
vector<int>num;
getline(cin, str);
for (int k = 0; k<str.length(); k++) {
if (str[k] == ' ' && !tmp.empty()) {
num.push_back(stoi(tmp));
tmp = "";
continue;
}
tmp += str[k];
}
if (!tmp.empty()) num.push_back(stoi(tmp));
for (int k = 1; k<num.size(); k++) {
MAP[axis(num[0]-1, num[k]-1)]++;
}
vector<long long int>hi;
for (int k = 0; k<M; k++) hi.push_back(0);
step.push_back(hi);
}
if (MAP[axis(N-1, M-1)] != 0 || MAP[axis(0, 0)] != 0) {
cout << 0 << "\n";
continue;
}
vector<pair<int, int>>start;
start.push_back(axis(0, 0));
step[0][0] = 1;
BFS(start);
cout << step[N-1][M-1] << "\n";
}
}
//ZeroJudge D198
//Dr. SeanXD