亚马逊经典面试题实例详解

/* 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 ] */

#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++; // 发现一个新陆地        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;}