[841] Keys and Rooms

啊～～～有點煩XD 覺得狀況很差

先來一個邊看邊寫的recursive

void dfs(int** rooms, int roomsSize, int* roomsColSize,int idx, bool* visted)

{

visted[idx]=true;

for (int i=0;i< roomsColSize[idx];i++)

{

if (visted[rooms[idx][i]]==false)

dfs(rooms, roomsSize, roomsColSize, rooms[idx][i],visted);

}

return;

}

bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize){

bool *visted = calloc (roomsSize, sizeof(bool));

dfs(rooms,roomsSize,roomsColSize,0,visted);

for (int i=0;i<roomsSize;i++)

if (visted[i]!=true)

return false;

return true;

}

然後是可以用stack 去寫

雖然我覺得用queue FIFO 好像更精確，不過題目不限制回傳的順序，那好像也沒差（？）

bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize){

bool *visted = calloc (roomsSize, sizeof(bool));

int *stack = malloc (sizeof(int)*roomsSize);

int pos= -1;

stack[++pos]=0;

visted[0]=true;

while (pos >=0)

{

int idx = stack[pos--];

for (int i=0;i<roomsColSize[idx];i++)

{

if (visted[rooms[idx][i]]==false)

{

stack[++pos] = rooms[idx][i];

visted[rooms[idx][i]]=true;

}

}

}

for (int i=0;i<roomsSize;i++)

if (visted[i]==false)

return false;

return true;

}