#include <bits/stdc++.h>
int actualNext(int move, int **board, int n)
{
int i = n-1;
int j = 0;
for (int k = 1; k < move; k++)
{
if (i%2==0)
{
if (j==n-1)
{
i--;
}
else
{
j++;
}
}
else
{
if (j==0)
{
i--;
}
else
{
j--;
}
}
}
if (board[i][j] == -1)
{
return move;
}
else
{
return board[i][j];
}
}
int minDiceThrowToLastCell(int **board, int n)
{
if (n == 1)
{
return 0;
}
int *arr = new int[n*n+1];
std::queue<int> q;
int visited = 1;
int branchCount = 0;//
int nextBranchCount = 1;//
int count = 1;//2
int curr = 0;//1
int next = 1;//1
arr[1] = visited;
q.push(1);
while (nextBranchCount)
{
branchCount = nextBranchCount;
nextBranchCount = 0;
while(branchCount)
{
curr = q.front();
q.pop();
branchCount--;
for (int i = 1; i <= 6 && curr + i <= n*n; i++)
{
next = actualNext(curr + i, board, n);
if (next == n*n)
{
delete[] arr;
return count;
}
else if (arr[next] != visited)
{
arr[next] = visited;
q.push(next);
nextBranchCount++;
}
}
}
count++;
}
delete[] arr;
return -1;
}
test case:
6
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 35 -1 -1 13 -1
-1 -1 -1 -1 -1 -1
-1 15 -1 -1 -1 -1
https://www.codingninjas.com/studio/problems/snake-and-ladder_630458?leftPanelTab=2
Coding Ninjas StudioCoding Ninjas Studiowww.codingninjas.com
댓글 0