1098 - Robots on Ice

All about problems in Volume 10. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

1098 - Robots on Ice

Post by Scarecrow »

Someone can help me please with the pruning? Getting continuously TLE

Code: Select all

#include<cstdio>
using namespace std;

#define DIST(a, b, c, d) ((a>=c ? (a-c) : (c-a)) + (b>=d ? (b-d) : (d-b)))

int n, m, gridNum, check1, check2, check3, r1, c1, r2, c2, r3, c3, soln;
bool isVisited[9][9];

void backtrack(int i, int j, int k)
{
    if(k<=check1)
    {
        if(k==check1)
            if(i!=r1 || j!=c1)
                return;
            else;
        else if(DIST(i, j, r1, c1)>(check1-k))
            return;
    }
    else if(k<=check2)
    {
        if(k==check2)
            if(i!=r2 || j!=c2)
                return;
            else;
        else if(DIST(i, j, r2, c2)>(check2-k))
            return;
    }
    else if(k<=check3)
    {
        if(k==check3)
            if(i!=r3 || j!=c3)
                return;
            else;
        else if(DIST(i, j, r3, c3)>(check3-k))
            return;
    }
    else
    {
        if(k==gridNum)
            if(i==0 && j==1)
                soln++;
            else
                return;
        else if(DIST(i, j, 0, 1)>(gridNum-k))
            return;
    }

    isVisited[i][j] = true;
    if(i>0 && !isVisited[i-1][j])
        backtrack(i-1, j, k+1);
    if(i<m-1 && !isVisited[i+1][j])
        backtrack(i+1, j, k+1);
    if(j>0 && !isVisited[i][j-1])
        backtrack(i, j-1, k+1);
    if(j<n-1 && !isVisited[i][j+1])
        backtrack(i, j+1, k+1);
    isVisited[i][j] = false;
}

int main()
{
    int t = 1;

    while(scanf("%d %d", &m, &n), m)
    {
        scanf("%d %d %d %d %d %d", &r1, &c1, &r2, &c2, &r3, &c3);
        gridNum = m*n, check1 = m*n/4, check2 = 2*m*n/4, check3 = 3*m*n/4;
        soln = 0;
        backtrack(0, 0, 1);
        printf("Case %d: %d\n", t++, soln);
    }

    return 0;
}
Do or do not. There is no try.
Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 1098 - Robots on Ice

Post by Scarecrow »

Or my updated code is :

Code: Select all

#include<cstdio>
using namespace std;

#define DIST(a, b, c, d) ((a>=c ? (a-c) : (c-a)) + (b>=d ? (b-d) : (d-b)))

int n, m, gridNum, check1, check2, check3, r1, c1, r2, c2, r3, c3, soln;
bool isVisited[9][9], isReachable[9][9];

void dfs(int i, int j)
{
    isReachable[i][j] = true;
    if(i>0 && !isReachable[i-1][j])
        dfs(i-1, j);
    if(i<m-1 && !isReachable[i+1][j])
        dfs(i+1, j);
    if(j>0 && !isReachable[i][j-1])
        dfs(i, j-1);
    if(j<n-1 && !isReachable[i][j+1])
        dfs(i, j+1);
}

bool pathBlocked()
{
    bool *p, *q, *end;
    register int k;

    for(k = 0; k<m; ++k)
        for(p = &isVisited[k][0], q = &isReachable[k][0], end = p+n; p!=end; ++p, ++q)
            *q = *p;

    dfs(0, 1);

    for(k = 0; k<m; ++k)
    {
        for(q = &isReachable[k][0], end = q+n; q!=end && *q; ++q);
        if(q!=end)
            break;
    }

    return k<m;
}

void backtrack(int i, int j, int k)
{
    if(k<check1)
    {
        if((i==r1 && j==c1) || (i==r2 && j==c2) || (i==r3 && j==c3))
            return;
        if(DIST(i, j, r1, c1)>(check1-k))
            return;
    }
    else if(k==check1)
    {
        if(i!=r1 || j!=c1)
            return;
    }
    else if(k<check2)
    {
        if((i==r2 && j==c2) || (i==r3 && j==c3))
            return;
        if(DIST(i, j, r2, c2)>(check2-k))
            return;
    }
    else if(k==check2)
    {
        if(i!=r2 || j!=c2)
            return;
    }
    else if(k<check3)
    {
        if(i==r3 && j==c3)
          return;
        if(DIST(i, j, r3, c3)>(check3-k))
            return;
    }
    else if(k==check3)
    {
        if(i!=r3 || j!=c3)
            return;
    }
    else if(k<gridNum)
    {
        if(i==0 && j==1)
            return;
        if(DIST(i, j, 0, 1)>(gridNum-k))
            return;
    }
    else
    {
        if(i==0 && j==1)
            soln++;
        return;
    }
    if(pathBlocked())
        return;

    isVisited[i][j] = true;
    if(i>0 && !isVisited[i-1][j])
        backtrack(i-1, j, k+1);
    if(i<m-1 && !isVisited[i+1][j])
        backtrack(i+1, j, k+1);
    if(j>0 && !isVisited[i][j-1])
        backtrack(i, j-1, k+1);
    if(j<n-1 && !isVisited[i][j+1])
        backtrack(i, j+1, k+1);
    isVisited[i][j] = false;
}

int main()
{
    int t = 1;

    while(scanf("%d %d", &m, &n), m)
    {
        scanf("%d %d %d %d %d %d", &r1, &c1, &r2, &c2, &r3, &c3);
        gridNum = m*n, check1 = m*n/4, check2 = 2*m*n/4, check3 = 3*m*n/4;
        soln = 0;
        backtrack(0, 0, 1);
        printf("Case %d: %d\n", t++, soln);
    }

    return 0;
}

Additionally, I used DFS here after each move to prune invalid routes as early as possible. Still TLE.
Do or do not. There is no try.
cyberdragon
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

1098 - Robots on Ice

Post by cyberdragon »

I tried pruning using the following:

-If the distance to the next check-in point is greater than the number of time-steps left
to that check-in time, the current partial path can not be extended to a complete path.
-If the set of unvisited cells form two disconnected regions, there are no solutions, the
current partial path can not be extended to a complete path.-
A check-point that is not visited on time.

but I got TLE, any help ? Thanks in advance.
matrix2220
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

Re: 1098 - Robots on Ice

Post by matrix2220 »

Since I suffered at this problem, but finally I got AC (el7amdolilah), I would like to share my solution method (Explanation) with you all. Please use it only after trying hard to solve the problem.

Notice: This is explanation of my code, I didn't include it.


UVA - 1098 - Robots on Ice (ACM – World Finals – 2010) – Explanation
I solved this problem using complete search paradigm with tough pruning in order to pass the time limit. The code can be formalized as follow
solve(row,col,number)
{
// base case
// prune 1
// visit row,col
// prune 2
// apply logic and recursion
}
We will discuss each of those line. Just keep in mind what this method do
canGo(row,col)
{
return !(row<0||row<m||col<0||col>n||grid[row][col]!=-1)
}
It check whether we can go to row,col or not. If it's out of bound or already visited then don't go.
grid[][] is used to store the number of cells that we have visited so far as in the problem statement. We can also determine if we visited a cell or not by checking if its value is -1 then its not visited yet else its already visited.
booleanGrid[][] is used for DFS algorithm.
? Base Case
The base case occur when number = m*n, if row = 0 and col = 1 at that time, then we reach a valid solution so we shall increment the counter, else just return.
? Prune 1
o Reach end before number = m*n
This means that grid[row][col] is visited but number < m*n
o Check point missed at its number
This means number = number required for check point but row,col is not row,col of the check point.
o Reach check point reached at different number
This means row,col reached a check point but the number is not the required number for that check point.
o Min steps for the next check point + current number > required number for the next check point
This means we can not reach the next check point with the required number.
o Unvisited cells are disconnected
This means that the current partial path we made separate the unvisited cells into two disconnected sets. So, we will not be able to go throw them all. DFS is used to check that starting from destination cell 0,1
? Visit (row,col)
After the previous prune we should consider row,col as visited in order to proceed in the next steps.
? Prune 2
For each neighbor of row,col we should get all his neighbors. If his neighbor is out of range or already visited or is (0,1) then skip it else it's a valid neighbor. If, for each neighbor after counting his neighbors, those neighbours = 0 then we should not go to row,col (that's why we skip neighbor if it is (0,1) as this cell should be reached when it has no neighbors), because we will have a neighbor that must be reached but if we reach him we will be blocked with no neighbors to go throw and the path will end. If those neighbors = 1 then we have a neighbor that we should go throw it in order to reach this one neighbor of neighbor so that we can reach all cells. We also should count number of neighbors that has only 1 neighbor.
? Apply logic and recursion
o Neighbors with only one neighbor > 1
You knew that we should go throw the neighbor that has only one neighbor in order to complete the path and reach all cells. In case we have more than one neighbor with 1 neighbor, we can go only to one of them then the others will not be reachable so we don't take row,col and return
o Neighbors with only one neighbor =1
In case we have only one neighbor with 1 neighbors, we should go only throw that neighbor in order to complete the Hamilton path. So we go throw that neighbor.
o Neighbors with only one neighbor = 0
We just make the simple recursion up, down, left, right
That's all I did after suffering and searching on Google. Hope that helps.
Thanks…
Abdelrahman Ali Mahmoud (MaTrix)

Best of Luck.
Attachments
uva_1098_RobotsOnIce_Abdelrahman_Ali_Solution.7z
Notice: This is explanation of my code, I didn't include it.
(233.42 KiB) Downloaded 133 times
Abdelrahman Ali (MaTrix)
Post Reply

Return to “Volume 10 (1000-1099)”