亞馬遜經(jīng)典面試題實例詳解
更新時間:2017年10月11日 14:19:43 作者:JeemyJohn
這篇文章主要介紹了亞馬遜經(jīng)典面試題實例詳解的相關(guān)資料,希望通過本文能幫助到大家,讓大家學(xué)習(xí)理解這部分內(nèi)容,需要的朋友可以參考下
亞馬遜面試題:
如下所示的Map中,0代表海水,1代表島嶼,其中每一個島嶼與其八領(lǐng)域的區(qū)間的小島能相連組成島嶼群。寫代碼,統(tǒng)計Map中島嶼個數(shù)。
/* Q1. Map [ 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ] */
實現(xiàn)代碼:
#include<iostream>
#include<queue>
using namespace std;
typedef struct {
int i;
int j;
}position;
void search(int a[][], int n, int i, int j, int cnt) {
queue<position> qu = new queue<position>();
position p;
p.i = i;
p.j = j;
qu.push(p);
a[i][j] = cnt;
while (!qu.empty()) {
p = qu.pop();
for (int ii = p.i - 1; ii <= p.i + 1; ii++) {
for (int jj = p.j - 1; jj <= p.j + 1; jj++) {
if (ii >= 0 && ii < n && jj >= 0 && jj < n && a[ii][jj] == 1 && (ii != i || jj != j)) {
a[ii][jj] = cnt;
p.i = ii;
p.j = jj;
qu.push(p);
}
}
}
}
}
int count(int a[][], int n) {
int cnt = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
cnt++; // 發(fā)現(xiàn)一個新陸地
search(a, n, i, j, cnt);
}
}
}
return cnt;
}
int main() {
int n;
cin >> n;
int a[][] = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
int cnt = count(a, n);
cout << cnt - 1 << endl;
return 0;
}
如有疑問請留言或者到本站社區(qū)交流討論,感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
相關(guān)文章
C語言之結(jié)構(gòu)體定義 typedef struct 用法詳解和用法小結(jié)
這篇文章主要介紹了C語言的結(jié)構(gòu)體定義typedef struct用法詳解和用法小結(jié),typedef是類型定義,typedef struct 是為了使用這個結(jié)構(gòu)體方便,感興趣的同學(xué)可以參考閱讀2023-03-03
C++11?std::transform函數(shù)使用小結(jié)
std::transform是C++標(biāo)準(zhǔn)庫中的一個算法,它用于對輸入范圍內(nèi)的元素進行操作,并將結(jié)果存儲在輸出范圍內(nèi),本文就介紹了std::transform函數(shù)的具體使用,感興趣的可以了解一下2023-09-09
C++ throw關(guān)鍵字實現(xiàn)拋出異常和異常規(guī)范
本文主要介紹了C++ throw關(guān)鍵字實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-08-08

