540C： Ice Cave

题目链接

题意：

n*m的地图，'X'表示有裂痕的冰块，'.'表示完整的冰块，有裂痕的冰块再被踩一次就会碎掉，完整的冰块被踩一次会变成有裂痕的冰块，

现在告诉起点和终点，问从起点能否走到终点并且使终点的冰块碎掉。不能原地跳。起点和终点可能会在同一个位置。

解题思路：

在只走‘.’的情况下把终点的冰踩碎

 

输入n*m的矩阵

以及走的开始和终点位置

在开始点，上下左右找‘.’，有就走，并把改点设置为‘X’，走到终点时候，若终点是‘X’则成功。

其他情况都失败。

 

这个程序是在codeforces上面抄的

Java程序：

import java.io.PrintWriter;

import java.util.Scanner;

public class C540 {

    static void run0() throws Exception {

        PrintWriter pw = new PrintWriter(System.out);

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int m = sc.nextInt();

        char[][] ch = new char[n][m];

        for(int i=0;i<n;i++)

            ch[i] = sc.next().toCharArray();

        int fromX = sc.nextInt() - 1;

        int fromY = sc.nextInt() -1;

        int toX = sc.nextInt() -1;

        int toY = sc.nextInt() -1;

        ch[fromX][fromY]='.';

        if(recur(ch,fromX,fromY,toX,toY)) pw.println("YES");

        else pw.println("NO");

        pw.close();

    }

    // 暴力破解，在四个方向做判断

    public static boolean recur(char[][] ch,int curX,int curY,int tX,int tY){

        // 越界失败

        if(curX<0 || curY<0 ||curX>=ch.length||curY>=ch[0].length) return false;

        // 走了回去，并且是在X的情况下，说明已经走了一次，或者 本来就是X

        if(curX==tX &&curY==tY &&ch[tX][tY]=='X') return true;

         // X 不可走

        if(ch[curX][curY]=='X') return false;

        // 是 点的 情况，可以走，走过设置为 X

         ch[curX][curY] = 'X';

        return recur(ch,curX-1,curY,tX,tY)||

               recur(ch,curX+1,curY,tX,tY)||

               recur(ch,curX,curY-1,tX,tY)||

               recur(ch,curX,curY+1,tX,tY);

    }

    public static void main(String[] args)  throws Exception{

        run0();

    }

}

上面的注释能很好的理解程序。

下面的程序和上面的差不多

也是复制别人的

import java.util.Scanner;

public class C540_1 {

    static int n;

    static int m;

    static char[][] map;

    static boolean[][] visited;

    static int pi[];

    static int pf[];

    static int[] R = new int[] {1, 0, -1, 0};

    static int[] C = new int[] {0, 1, 0, -1};

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        n=sc.nextInt();

        m= sc.nextInt();

        map = new char[n][m];

        visited = new boolean[n][m];

        for(int i=0;i<n;++i){

            String s=sc.next();

            for(int j=0;j<m;j++){

                map[i][j] = s.charAt(j);

                visited[i][j] = false;

            }

        }

        pi = new int[]{sc.nextInt()-1,sc.nextInt()-1};

        pf = new int[]{sc.nextInt()-1,sc.nextInt()-1};

        if(dfs(pi[0],pi[1])) System.out.println("YES");

        else System.out.println("NO");

    }

    static boolean dfs(int r,int c){

        // 走过的点设置为 true

        visited[r][c] = true;

        // 改点走后设置为 X

        map[r][c]='X';

        for(int k=0;k<4;++k){

            int rr = r+R[k];

            int cc = c+C[k];

            if(rr>=0 && rr<n &&cc>=0 &&cc< m){

                if(rr==pf[0] &&cc==pf[1] &&map[rr][cc]=='X')

                    return true;

                // !=X  没有被访问过 ，当前点可以走

                else if(map[rr][cc]!='X' && visited[rr][cc] ==false &&dfs(rr,cc))

                    return true;

            }

        }

        return false;

    }

}