10452 - Marcus

[Obaida]

I think this is an easy problem.
Easy recursive formula works here.
I just searched for the next match until last one.

[anis_cuet016]

hlw vahid sanei ......
you asked for the recursive code .....
please others don't just go through the code .... otherwise u will loose the interest of solving ....
can please share how u tracked the given path in BFS ????


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define MAX 10

#define FORTH 1
#define LEFT 2
#define RIGHT 3

char mat[MAX][MAX];
int row, col;
int sx, sy, dx, dy;

char lim[] = { 'I', 'E', 'H', 'O', 'V', 'A', '#' };
int R[] = { 0, -1, 0};
int C[] = {-1, 0, 1};

void read_input()
{
int i, j;

scanf("%ld %ld", &row, &col);
for(i=0; i<row; i++)
{
getchar();
for(j=0; j<col; j++)
{
scanf("%c", &mat[j]);

if(mat[j] == '@')
sx = i, sy = j;
else if(mat[j] == '#')
dx = i, dy = j;
}
}

return ;
}

int dir[MAX * MAX];
int flag = true;

void DFS(int x, int y, char ch, int level)
{
int i;

if( (mat[x][y] == '#') || (x == dx && y == dy) )
{
flag = false;
return ;
}

for(i = 0; flag && i < 3; i++)
{
int nr = R + x;
int nc = C + y;

if(nr < 0 || nc < 0 || nr > row || nc > col)
continue;

if(mat[nr][nc] == ch)
{
mat[nr][nc] = '.';
ch = lim[level];

if( nr == x && nc < y )
dir[level] = LEFT;
else if( nr == x && nc > y )
dir[level] = RIGHT;
else if( nr < x && y == nc )
dir[level] = FORTH;

DFS(nr, nc, lim[level + 1], level + 1);
}
}

}

void print()
{
for(int i = 0; i <= 5; i++)
{
if(dir == 1)
printf("forth ");
else if(dir == 2)
printf("left ");
else if(dir == 3)
printf("right ");

dir = 0;
}
printf( dir[6] == 1 ? "forth" : dir[6] == 2 ? "left" : "right");
dir[6] = 0;

printf("\n");
}

void init()
{
int i, j;

for(i = 0; i <= row; i++)
for(j = 0; j <= col; j++)
mat[j] = 0;
flag = true;
}

int main()
{
// freopen("in.txt", "r", stdin);
int Case;

scanf("%d", &Case);
while(Case--)
{
read_input();
DFS(sx, sy, lim[0], 0);
print();

init();
}
return 0;
}

[Samleo]

Hi, I got WA for my code (below) and I really can't understand why. Can someone help me to see if there is something wrong with my code? Thanks. (It's recursive code btw)

#include <iostream>
#include <fstream>
#include <math.h>
#include <string.h>

using namespace std;

#define LOOP(times) for(int(i)=0;i<int(times);i++);

char stones[10][10];
char letters[6] = {'I','E','H','O','V','A'};

void checkStones(int row, int col, int steps){
if(steps<6){ //see if coming to end
if(stones[row][col-1] == letters[steps]){ //left
cout << "left ";
checkStones(row,col-1,steps+1);
//return
}
else if(stones[row][col+1] == letters[steps]){ //right
cout << "right ";
checkStones(row,col+1,steps+1);
//return;
}
else if(stones[row-1][col] == letters[steps]){ //forth
cout << "forth ";
checkStones(row-1,col,steps+1);
//return;
}
else{
//something wrong..
return;
}
}
else{
if(stones[row][col-1] == '#'){ //left
cout << "left" << endl;
//return;
}
else if(stones[row][col+1] == '#'){ //right
cout << "right" << endl;
//return;
}
else if(stones[row-1][col] == '#'){ //forth
cout << "forth" << endl;
//return;
}
else{
//something is not right...
//system("pause");
return;
}
}

return;
}

int main(){
int n;
int rows, cols, startRow, startCol;

//ifstream cin;
//cin.open("temp.in");

cin >> n;

LOOP(n){
cin >> rows >> cols;
for(int b=1;b<=rows;b++){
for(int c=1;c<=cols;c++){
cin >> stones[c];
if(stones[c] == '@'){
startRow = b;
startCol = c;
}
}

}

checkStones(startRow,startCol,0);
//memset(stones, 'B', sizeof(stones[0][0])*10*10); //array must be reset to random char avoid conflict during search

}

//system("pause");
return 0;
}

[brianfry713]

Doesn't match the sample I/O. Use the code blocks.

[Shahidul.CSE]

Code: Select all

Ac

[brianfry713]

Change line 50 to:
if(row > 0 && (grid[row-1][p]=='I'||grid[row-1][p]=='E'||grid[row-1][p]=='H'||grid[row-1][p]=='O'||grid[row-1][p]=='V'||grid[row-1][p]=='A'))

[Shahidul.CSE]

Thanks. Now got Accepted!