You are not logged in. Please login at www.codechef.com to post your questions!

×

Meduvada: WA

I was attempting this problem: http://opc.iarcs.org.in/index.php/problems/MEDUVADA

And I am getting WA (idk why). My approach is correct but I think there is a small mistake. My code:

#include<iostream>
#include<queue>
#include<utility>
#include<cstdlib>
using namespace std;

int mod(int a, int b)
{
    if(a < 0) return a+b;
    else return a%b;
}

int main()
{
    int r,c;
    cin >> r >> c;
    char maze[r][c];
    pair<int,int> sp;
    pair<int,int> ep;
    for(int i = 0;i < r;i++)
    {
        for(int j = 0;j < c;j++)
        {
            cin >> maze[i][j];
            if(maze[i][j] == 'M') sp = make_pair(i,j);
            if(maze[i][j] == 'D') ep = make_pair(i,j);
        }
    }
    char path[r][c];
    for(int i = 0;i < r;i++) for(int j = 0;j < c;j++) path[i][j] = '.';
    bool visit[r][c];
    for(int i = 0;i < r;i++) for(int j = 0;j < c;j++) visit[i][j] = false;
    queue< pair<int,int> > bfs;
    bfs.push(sp);
    while(!bfs.empty())
    {
        int x = bfs.front().first;
        int y = bfs.front().second;
        if(x == ep.first && y == ep.second) break;
        bfs.pop();
        int temp1, temp2;
        temp1 = mod(x+1,r);
        temp2 = mod(y,c);
        if(!visit[temp1][temp2] && maze[temp1][temp2] != '#')
        {
            visit[temp1][temp2] = true;
            path[temp1][temp2] = 'u';
            bfs.push(make_pair(temp1,temp2));
        }
        temp1 = mod(x-1,r);
        temp2 = mod(y,c);
        if(!visit[temp1][temp2] && maze[temp1][temp2] != '#')
        {
            visit[temp1][temp2] = true;
            path[temp1][temp2] = 'd';
            bfs.push(make_pair(temp1,temp2));
        }
        temp1 = mod(x,r);
        temp2 = mod(y+1,c);
        if(!visit[temp1][temp2] && maze[temp1][temp2] != '#')
        {
            visit[temp1][temp2] = true;
            path[temp1][temp2] = 'l';
            bfs.push(make_pair(temp1,temp2));
        }
        temp1 = mod(x,r);
        temp2 = mod(y-1,c);
        if(!visit[temp1][temp2] && maze[temp1][temp2] != '#')
        {
            visit[temp1][temp2] = true;
            path[temp1][temp2] = 'r';
            bfs.push(make_pair(temp1,temp2));
        }
    }
    int x = ep.first, y = ep.second;
    if(visit[x][y] == false) {
        cout << "NO" << endl;
        return 0;
    }
    for(int i = 0;i < r;i++) {for(int j = 0;j < c;j++) cout << path[i][j]; cout << endl;}
    cout << "YES" << endl;
    while(1)
    {
        if(x == sp.first && y == sp.second) break;
        maze[x][y] = 'x';
        if(path[x][y] == 'u') x = mod(x-1,r);
        else if(path[x][y] == 'd') x = mod(x+1,r);
        else if(path[x][y] == 'l') y = mod(y-1,c);
        else y = mod(y+1,c);
    }
    maze[ep.first][ep.second] = 'D';
    for(int i = 0;i < r;i++)
    {
        for(int j = 0;j < c;j++) cout << maze[i][j];
        cout << endl;
    }
    return 0;
}

Code explanation: The array 'path' stores the parent of that point and the rest is bfs. I have made mod function since we can go from left and reach the right most end of the gird.

asked 22 Jan '15, 13:58

ketanhwr's gravatar image

6★ketanhwr
1.9k31844
accept rate: 15%

I believe the test data is wrong

(22 Jan '15, 14:32) superty3★

No, I don't think so.

(22 Jan '15, 21:33) ketanhwr6★

Which test cases are right for you? For me it was 1, 6, 9 (0-indexed). If yours are the same it is surely not coincidence. I am too lazy to download the test data and check though you may do so if you wish.

(22 Jan '15, 22:30) superty3★

Lol I am getting AC in the same tests!

(23 Jan '15, 17:20) ketanhwr6★

Anyway, I checked the test data and it is clearly wrong. They mentioned that there can be multiple outputs but they didn't check for them :/

(23 Jan '15, 17:34) ketanhwr6★

Yep. Generally if I'm not getting AC in extremely easy questions like this on the IARCS server I don't bother wasting my time. A lot of problems have wrong testdata there.

(23 Jan '15, 18:59) superty3★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,019
×463
×109
×9

question asked: 22 Jan '15, 13:58

question was seen: 561 times

last updated: 23 Jan '15, 18:59