T245982 "kdoi-01" drunken flower Yin

「KDOI-01」 Drunk flower Yin

Background

lately ,kdy Fell in love with a game . In the game , He plays a carefree white goose .

Now? , He is controlling the white goose to complete the final task .

  Title Description

The white goose is now in a n*m   In the maze of , The maze consists of numbers 0  and 1  form , If the number on a lattice is 0, It means that this place is passable , if 1, It means this place is impassable . At first , It is located in (a,b)  The location of , And the exit is (c,d). The coordinates of the upper left corner of the matrix are (1,1), The coordinates in the lower right corner are (n,m).

unfortunately , In this maze k  Hunter , They will pose a threat to the white goose . When the two coordinates are the same , The goose will be caught , Whether at the entrance or exit .

Hunter and goose can move one unit per second , Of course, they can also not move . Both start moving at the same time, and they can only move up, down, left, right . Now he wants to know , Is it possible for white geese to get out of the maze without being caught by hunters , We assume that these hunters are smart enough .

kdy  I want you to help him calculate , Can the goose escape the maze . because kdyl  And play bizhoumu , So he only gave you 500ms  Time for .

  Input format

There are many sets of data in this question , First line a positive integer t, Is the number of data sets . Next t Group data , For each set of data ：

Two positive integers in the first line n  and m.

Next, enter a n  That's ok m  Columns of the matrix , The matrix will only consist of 0  and 1  form .

Next is an integer k, Indicates the number of hunters .

Next k  That's ok , Two positive integers per line , Express k  The initial coordinates of a hunter .

Four integers in the last line a,b,c,d, Represents the coordinates of the entrance and exit .

All coordinates involved in this problem are in the map and will not be located at obstacles .

  Output format

For each set of data , If the goose can successfully walk out of the maze without being caught , Output 'T', Otherwise output 'F'.

  Examples 1

The sample input 1
2
3 4
0100
0011
1001
2
1 1
1 4
2 2 3 2
2 2
01
10
0
1 1 2 2

Sample output 1
T
F

  Tips

Sample explanation ：

For the first set of data , Draw a schematic diagram as follows ：

The white goose obviously won't be caught up .

For the second set of data , The big white goose can't reach the end .

This question is tested with bundled data .

 - Subtask 0（10 pts）：k=0.
 - Subtask 1（10 pts）：n,m<=10.
 - Subtask 2（30 pts）：k<=10^2.
 - Subtask 3（50 pts）： No special restrictions .
 
For all data ,n,m<=10^3,k<=n*m,t<=10.

First of all, if there is a way for the big white goose to reach the end （ Forget about hunters ）, We are thinking about hunters .

Otherwise, there is no way for the big white goose to output directly at the end ‘F’ Just go .

Because of the bfs Search for , Step by step, we find the path from the big white goose to the destination , If the hunter's path is greater than the path of the big white goose to the end , You can't catch up with the big white goose .（ We can assume such a model , The goose and the hunter race on a straight track , They have the same speed , It depends on who gets away from the finish line , Whoever wins , You can draw a diagram on the draft paper ）

Then the next step is set bfs The template , Don't understand bfs You can read my previous blog */

Here's the code

#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
int max_step1 = 0;
int temp_step1 = 0;
int n, m;
bool vis[1000][1000];
string maze[1000];
int hunterx[1000000];
int huntery[1000000];
int dir[4][2] = {
   {-1, 0}, {0, -1}, {1, 0}, {0, 1}};             /* Direction */
int start_x, start_y, end_x, end_y;
struct node                                                    /* Structure */
{
    int x, y, step;
    node(int _x, int _y, int _step)
    {
        x = _x;
        y = _y;
        step = _step;
    }
};
void speed()                                                   /* send cin have scanf Same speed */
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}
bool in(int x, int y)                                         /* Is it across the border? */
{
    return x >= 0 && x < n && y >= 0 && y < m;
}
bool bfs1(int x, int y)                                      /* Breadth search */
{
    queue<node> q;
    q.push(node(x, y, 0));
    vis[x][y] = 1;
    while (!q.empty())
    {
        node temp = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tx = temp.x + dir[i][0];
            int ty = temp.y + dir[i][1];
            if (in(tx, ty))
            {
                if (maze[tx][ty] != '1' && !vis[tx][ty])
                {
                    if (tx == end_x && ty == end_y)
                    {
                        max_step1 = temp.step + 1;         /* If you can reach the end, take out the steps to the end */
                        return true;
                    }
                    else
                    {
                        vis[tx][ty] = 1;
                        q.push(node(tx, ty, temp.step + 1));
                    }
                }
            }
        }
    }
    return false;
}
bool bfs2(int x, int y)
{
    queue<node> q;
    q.push(node(x, y, 0));
    vis[x][y] = 1;
    if (x == start_x && y == start_y)                      /* Prevent exceptions */
    {
        return true;
    }
    while (!q.empty())
    {
        node temp = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tx = temp.x + dir[i][0];
            int ty = temp.y + dir[i][1];
            if (in(tx, ty))
            {
                if (maze[tx][ty] != '1' && !vis[tx][ty])
                {
                    if (tx == end_x && ty == end_y)
                    {
                        temp_step1 = temp.step + 1;     /* The distance from the hunter to the end */
                        return true;
                    }
                    else
                    {
                        vis[tx][ty] = 1;
                        q.push(node(tx, ty, temp.step + 1));
                        if (temp.step + 1 > max_step1)  /* prune */
                        {
                            return false;
                        }
                    }
                }
            }
        }
    }
    return false;
}
int main()
{
    speed();
    int t;
    cin >> t;
    while (t > 0)
    {
        cin >> n >> m;
        bool flag = true;
        memset(vis, 0, sizeof(vis));
        max_step1 = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> maze[i];
        }
        int k;
        cin >> k;
        for (int i = 0; i < k; i++)
        {
            cin >> hunterx[i] >> huntery[i];
            hunterx[i]--;
            huntery[i]--;
        }
        cin >> start_x >> start_y >> end_x >> end_y;
        start_x--;
        start_y--;
        end_x--;
        end_y--;
        if (start_x == end_x && start_y == end_y)
        {
            cout << 'T' << endl;
        }
        else
        {
            if (bfs1(start_x, start_y) == false)                     /* If the goose can't reach the end */
            {
                cout << 'F' << endl;
            }
            else
            {
                for (int i = 0; i < k; i++)
                {
                    memset(vis, 0, sizeof(vis));
                    temp_step1 = 0;
                    if (bfs2(hunterx[i], huntery[i]) == true && temp_step1 <= max_step1)     /* If the hunter arrives faster than the big white goose */
                    {
                        flag = false;
                        cout << 'F' << endl;
                        break;
                    }
                }
                if (flag == true)
                {
                    cout << 'T' << endl;
                }
            }
        }
        t--;
    }
    return 0;
}