範例程式碼 uva722
//uva722
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <deque>
#define SIZE (2 + 99)
using namespace std;
// 紀錄坐標軸
struct Point {
int x;
int y;
Point(int a, int b)
{
x = a;
y = b;
}
};
// 檢查是否存在於 Deque 中
bool findInDeque(deque<Point> myDeque, Point myPoint) {
for(int f = 0; f < myDeque.size(); f++) {
if(myDeque[f].x == myPoint.x && myDeque[f].y == myPoint.y)
return true;
}
return false;
}
int main()
{
int caseNum, sX, sY, row, column, path;
char area[SIZE][SIZE], buf[SIZE];
deque<Point> myQue;
cin >> caseNum; // get case number
for(int c = 0; c < caseNum; c++) {
// 每個 case 之間要空一行隔開
if(c != 0)
cout << endl;
// initialize
myQue.clear();
column = 0;
path = 0;
for(int i = 0; i < SIZE; i++)
for(int j = 0; j < SIZE; j++)
area[i][j] = '1';
// get start point
cin >> sX >> sY;
getchar(); // 處理測值間的空白行
cin.getline(buf, SIZE); // read data
row = strlen(buf); // calculate how many rows
while(strlen(buf) != 0) {
column++; // calculate how many columns
strncpy(area[column] + 1, buf, strlen(buf)); // puts into my array
cin.getline(buf, SIZE); // read data
}
// use BFS to find the answer
myQue.push_back(Point(sX, sY)); // push start point to deque
while(!myQue.empty()) { // end for empty
int nX, nY;
// 記錄成 nX, nY 避免寫太長
nX = myQue.front().x;
nY = myQue.front().y;
// if 初始位置是 land 則不需要動作
if(area[nX][nY] == '1') {
path = 0;
break;
}
// 紀錄走過的位置
area[nX][nY] = '2';
path++;
// 檢查其他能走的位置
if(area[nX - 1][nY] == '0' && !findInDeque(myQue, Point(nX - 1, nY)))
myQue.push_back(Point(nX - 1, nY));
if(area[nX + 1][nY] == '0' && !findInDeque(myQue, Point(nX + 1, nY)))
myQue.push_back(Point(nX + 1, nY));
if(area[nX][nY - 1] == '0' && !findInDeque(myQue, Point(nX, nY - 1)))
myQue.push_back(Point(nX, nY - 1));
if(area[nX][nY + 1] == '0' && !findInDeque(myQue, Point(nX, nY + 1)))
myQue.push_back(Point(nX, nY + 1));
// 做完後從 deque pop 掉
myQue.pop_front();
}
// output final answer
cout << path << endl;
}
return 0;
}