Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.6 kB
4
Indexable
Never
#include<stdio.h>
#include<stdbool.h>

bool arrive = false;
int n,m;

bool walk(char map[n][m+1], int row, int column, int n_tele, int teleport[n*m][2], bool walked[n][m]);

int main()
{
    int t;
    scanf("%d", &t);

    while(t--)
    {
        scanf("%d %d", &n, &m);
        char map[n][m+1];
        int count = 0;
        int teleport[n*m][2];
        bool walked[n][m];

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
                walked[i][j] = false;
        }

        for(int i=0; i<n; i++)
        {
            scanf("%s", &map[i]);
            for(int j=0; j<m; j++)
            {
                if(map[i][j] == 'T')
                {
                    teleport[count][0] = i;
                    teleport[count][1] = j;
                    count++;
                }
            }
        }
        
        arrive = walk(map,0,0,count,teleport,walked);

        if(arrive)
            printf("Yes\n");
        else
            printf("No\n");
        
        arrive = false;
    }

    return 0;
}

bool walk(char map[n][m+1], int row, int column, int n_tele, int teleport[n*m][2], bool walked[n][m])
{
    walked[row][column] = true;
    
    if(row == n-1 && column == m-1)
    {
        return true;
    }
    else
    {
        if(map[row][column+1]!='#' && column+1<m && !walked[row][column+1])
        {
                if(walk(map,row,column+1,n_tele,teleport,walked))
                            return true;
        }
        if(map[row][column-1]!='#' && column-1>=0 && !walked[row][column-1])
        {
                if(walk(map,row,column-1,n_tele,teleport,walked))
                            return true;
        }
        if(map[row+1][column]!='#' && row+1<n && !walked[row+1][column])
        {
                if(walk(map,row+1,column,n_tele,teleport,walked))
                            return true;
        }
        if(map[row-1][column]!='#' && row-1>=0 && !walked[row-1][column])
        {
                if(walk(map,row-1,column,n_tele,teleport,walked))
                            return true;
        }
        if(map[row][column] == 'T')
        {
            for(int i=0; i<n_tele; i++)
            {
                if(!walked[teleport[i][0]][teleport[i][1]])
                {
                    if(walk(map,teleport[i][0],teleport[i][1],n_tele,teleport,walked))
                        return true;
                }
            }
        }
    }

    return false;
}