【9度】タイトル1461：Tempter of the bone

6943 ワード

タイトルの住所:http://ac.jobdu.com/problem.php?pid=1461 テーマの説明:
The doggie found a bone in ancint maze、which fascinated hia lot.However、when he picked it up、the maze began to shak、and the doggie could feel the ground sinking.He realized ththe boneそして、he tried desperateely to get out of this maze.The maze was a rectanggle with sizs N by M.The was a door in the maze.At the begining、the door was closed and it would would open the T T T T T T T T T the T T T T T T T T T T T T T T-th thet thet t t t t t thet t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t t thethethet t t thet t t t t t t t t t t t t t t second.In every second、he could move block to one block to of the uper、lower、left and right neigboininininininingblocks.Onece hentered a block、the ground of thisblock would start sink and disappeathe nexxxxsecond.Hecould d d.Hecould d d d lolololololot second.Hecocococococolod d d d d d d blblblblblblblbloud.Hecococococococococococococococolod d d d d d d d d d d d d blblblblblblblblblblblblblblblblblblblblPlease help him.
入力:
The input consists of multile test cases.The first line of each test case contains three integers N，M，and T(1出力:
For each test case，print in one line“YES”if the doggie can survive，or“NO”others wise.
サンプル入力：

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

サンプル出力:

NO
YES

タイトルの大意: 犬が迷宮の中で骨を見つけましたが、骨を拾ったのは地面が揺れ始めました。彼は今迷宮から脱出します。彼は毎回左右の方向に移動することができます。第T秒で迷路の出口のドアが開きます。彼が迷路から脱出できるかどうか聞いてみます。テーマ分析: 迷宫の类似の问题を解决して、もし到着することができるかどうかならば、普通はdfsを选んで使って、もし最も短い歩数を求めるならば、普通はbfsを选びます。基本的な考え方: この問題はイエスかノーかを要求しますので、dfsを選択してください。 1、入力データを構造体に記憶する。 2、スタートノードから順番にアクセスして、出口が発見されました。時間はちょうどTに等しいです。さもなければサイクルが終わるまで続けます。 3、印刷結果を比較する。C++ACコード

#include <stdio.h>
#include <stdlib.h>
#include<queue>
using namespace std;
const int maxn = 8;
int visit[maxn][maxn];
char mazeArr[maxn][maxn];
int step[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int n , m ,t;
bool success;
int i,j;
    
void dfs(int x, int y ,int time) {
    for (int i = 0; i < 4; i++) {
        int sx = x + step[i][0];
        int sy = y + step[i][1];
        if (sx < 0 || sy < 0 || sx > n-1 || sy > m-1){
            continue;
        }
        if (mazeArr[sx][sy] == 'X') {
            continue;
        }
        if (visit[sx][sy] == 1) {
            continue;
        }
              
        if (mazeArr[sx][sy] == 'D') {
            if (time + 1 == t) {
                success = true;
                return;
            }else {
                continue;
            }
        }
        visit[sx][sy] = 1;
        dfs(sx, sy, time+1);
        visit[sx][sy] = 0;
        if (success) {
            return;
        }
    }
}
  
int main(){ 
  
    while(scanf("%d%d%d",&n,&m,&t) != EOF ){
        if(n == 0 && m ==0 && t == 0){
            break;
        }
  
        for(i = 0; i < n ; i++){
            scanf("%s",mazeArr[i]);
                  
        }
        int startx;
        int starty;
        for( i = 0; i < n ; i++){
            for(j = 0; j < m ; j++){
                if(mazeArr[i][j] == 'S'){
                    startx = i;
                    starty = j;
                }
                visit[i][j] = 0;
            }
        }
        success = false;
        dfs(startx , starty, 0);
        printf("%s
", success == true ? "YES":"NO");
    }
     
    return 0;
}
/**************************************************************
    Problem: 1461
    User: wangzhenqing
    Language: C++
    Result: Accepted
    Time:10 ms
    Memory:1020 kb
****************************************************************/

Java ACコード

import java.util.Scanner;
  
public class Main {
    /*
     * 1461
     */
    private static char mazeArr[][];
    private static int visit[][];
    private static int step[][] = {{-1,0},{1,0},{0,-1},{0,1}};
    private static int n ,m ,t;
    private static boolean success;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            t = scanner.nextInt();
            if (n == 0 && m == 0 && t == 0) {
                break;
            }
            mazeArr = new char[n][m];
            visit = new int[n][m];
            for (int i = 0; i < n; i++) {
                String tempStr = scanner.next();
                mazeArr[i] = tempStr.toCharArray();
            }
            int startx = 0;
            int starty = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (mazeArr[i][j] == 'S') {
                        startx = i;
                        starty = j;
                    }
                }
            }
             
            success = false;
            dfs(startx, starty, 0);
            if (success) {
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }
 
    private static void dfs(int x, int y, int time) {
        for (int i = 0; i < 4; i++) {
            int sx = x + step[i][0];
            int sy = y + step[i][1];
            if (sx < 0 || sy < 0 || sx > n-1 || sy > m-1){
                continue;
            }
            if (mazeArr[sx][sy] == 'X') {
                continue;
            }
            if (visit[sx][sy] == 1) {
                continue;
            }
             
            if (mazeArr[sx][sy] == 'D') {
                if (time + 1 == t) {
                    success = true;
                    return;
                }else {
                    continue;
                }
            }
            visit[sx][sy] = 1;
            dfs(sx, sy, time+1);
            visit[sx][sy] = 0;
            if (success) {
                return;
            }
        }
    }
}
 
/**************************************************************
    Problem: 1461
    User: wzqwsrf
    Language: Java
    Result: Accepted
    Time:170 ms
    Memory:19760 kb
****************************************************************/

uva 10125-Sumsets（技巧的列挙）

Android指紋識別