第19章 广度优先搜索的状态表示

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int N = 110,INF = 0x3f3f3f3f;
    static int n,m,k;
    static int[][] dist = new int[N][N];//表示该位置需要转多少次才到
    static char[][] g = new char[N][N];
    static int x1,y1,x2,y2;
    static int[] dx = new int[] {0,-1,0,1};
    static int[] dy = new int[] {-1,0,1,0};
    static boolean bfs()
    {
        Queue<Pair> q = new LinkedList<Pair>();
        dist[x1][y1] = 0;
        for(int i = 0;i < 4;i ++)
        {
            int a = x1 + dx[i];
            int b = y1 + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] == '*') continue;
            q.add(new Pair(a,b,(i + 2) % 4));
            dist[a][b] = 0;
        }
        while(!q.isEmpty())
        {
            Pair t = q.poll();
            for(int i = 0;i < 4;i ++)
            {
                int a = t.x + dx[i];
                int b = t.y + dy[i];
                if(a < 0 || a >= n || b < 0 || b >= m) continue;
                if(g[a][b] == '*') continue;
                if(dist[a][b] <= dist[t.x][t.y]) continue;//转弯次数比它少
                q.add(new Pair(a,b,i));
                dist[a][b] = dist[t.x][t.y] + (i == t.dir ? 0 : 1);
            }
        }
/*      for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < m;j ++)
            {
                System.out.print(dist[i][j] + " ");
            }
            System.out.println();
        }*/
        return dist[x2][y2] <= k;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T -- > 0)
        {
            String[] s1 = br.readLine().split(" ");
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);
            for(int i = 0;i < n;i ++) Arrays.fill(dist[i], INF);
            for(int i = 0;i < n;i ++)
            {
                char[] temp = br.readLine().toCharArray();
                for(int j = 0;j < m;j ++)
                {
                    g[i][j] = temp[j];
                }
            }
            String[] s2 = br.readLine().split(" ");
            k = Integer.parseInt(s2[0]);
            x1 = Integer.parseInt(s2[1]);
            y1 = Integer.parseInt(s2[2]);
            x2 = Integer.parseInt(s2[3]);
            y2 = Integer.parseInt(s2[4]);
            g[x2][y2] = '.';
            if(bfs()) System.out.println("yes");
            else System.out.println("No");
        }
        
    }
}
class Pair
{
    int x,y,dir;//往dir方向走到达(x,y)，转弯的次数是k
    Pair(int x,int y,int dir)
    {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
}