HDU 1728迷宮から脱出(簡単dfs)
3757 ワード
迷宮から逃げる
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11863 Accepted Submission(s): 2858
Problem Description
mを1つ与える× n(m行、n列)の迷路、迷路の中には2つの位置があり、gloriaは迷路の1つの位置から別の位置に行きたいと思っています.もちろん迷路の中には空き地があり、gloriaは通り抜けることができます.障害がある場所もあります.彼女は迂回しなければなりません.迷路の1つの位置から、それに隣接する4つの位置までしか歩けません.もちろん、歩いているうちにgloriaは迷路の外に行けません.頭が痛いのは、gloriaは方向感覚のない人なので、彼女は歩いている間に、あまり曲がってはいけません.そうしないと、彼女は気絶します.与えられた2つの位置は空き地であると仮定し,初期にgloriaが向いている方向は未定であり,彼女は4つの方向のいずれかを選択して出発することができ,1回のカーブではない.gloriaは一つの位置から別の位置に行けますか?
Input
第1の挙動は整数t(1≦t≦100)であり、試験データの個数を表し、次にt群の試験データであり、各群の試験データにおいて、
第1の動作は2つの整数m,n(1≦m,n≦100)であり、それぞれ迷路の行数と列数を表し、次にm行であり、各行はn文字を含み、文字'.'はその位置が空き地であることを示し、文字'*'はその位置が障害であることを示し、入力データにはこの2つの文字しかなく、各テストデータの最後の動作は5つの整数k,x
1, y
1, x
2, y
2 (1 ≤ k ≤ 10, 1 ≤ x
1, x
2 ≤ n, 1 ≤ y
1, y
2 ≦m)で、kはgloriaが最も回転可能な曲げ数を表し、(x
1, y
1), (x
2, y
2)は、xの2つの位置を表す
1,x
2対応列、y
1, y
2対応する行.
Output
各テストデータのセットは1行に対応し、gloriaが1つの位置から別の位置に移動できれば「yes」を出力し、そうでなければ「no」を出力する.
Sample Input
Sample Output
Source
「ネット新恩普杯」杭州電子科学技術大学プログラム設計招待試合
テーマ:
n*nの図をあげて、kをあげて、起点と終点をあげます.回転方向K回以内に始点から終点に着くかどうか聞いてみます.問題が入力した座標に少し穴があることに注意してください.
解題構想:比較的簡単なdfsで,開始方向を−1に設定し,0,1,2,3を4方向に表す.ステアリングステップ数に1を加えると、各点に最小のステアリング回数が記録される.
迷宮から逃げる
ACコード:
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11863 Accepted Submission(s): 2858
Problem Description
mを1つ与える× n(m行、n列)の迷路、迷路の中には2つの位置があり、gloriaは迷路の1つの位置から別の位置に行きたいと思っています.もちろん迷路の中には空き地があり、gloriaは通り抜けることができます.障害がある場所もあります.彼女は迂回しなければなりません.迷路の1つの位置から、それに隣接する4つの位置までしか歩けません.もちろん、歩いているうちにgloriaは迷路の外に行けません.頭が痛いのは、gloriaは方向感覚のない人なので、彼女は歩いている間に、あまり曲がってはいけません.そうしないと、彼女は気絶します.与えられた2つの位置は空き地であると仮定し,初期にgloriaが向いている方向は未定であり,彼女は4つの方向のいずれかを選択して出発することができ,1回のカーブではない.gloriaは一つの位置から別の位置に行けますか?
Input
第1の挙動は整数t(1≦t≦100)であり、試験データの個数を表し、次にt群の試験データであり、各群の試験データにおいて、
第1の動作は2つの整数m,n(1≦m,n≦100)であり、それぞれ迷路の行数と列数を表し、次にm行であり、各行はn文字を含み、文字'.'はその位置が空き地であることを示し、文字'*'はその位置が障害であることを示し、入力データにはこの2つの文字しかなく、各テストデータの最後の動作は5つの整数k,x
1, y
1, x
2, y
2 (1 ≤ k ≤ 10, 1 ≤ x
1, x
2 ≤ n, 1 ≤ y
1, y
2 ≦m)で、kはgloriaが最も回転可能な曲げ数を表し、(x
1, y
1), (x
2, y
2)は、xの2つの位置を表す
1,x
2対応列、y
1, y
2対応する行.
Output
各テストデータのセットは1行に対応し、gloriaが1つの位置から別の位置に移動できれば「yes」を出力し、そうでなければ「no」を出力する.
Sample Input
2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
Sample Output
no
yes
Source
「ネット新恩普杯」杭州電子科学技術大学プログラム設計招待試合
テーマ:
n*nの図をあげて、kをあげて、起点と終点をあげます.回転方向K回以内に始点から終点に着くかどうか聞いてみます.問題が入力した座標に少し穴があることに注意してください.
解題構想:比較的簡単なdfsで,開始方向を−1に設定し,0,1,2,3を4方向に表す.ステアリングステップ数に1を加えると、各点に最小のステアリング回数が記録される.
迷宮から逃げる
ACコード:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int m, n, ex, ey, k, p[105][105];
//p[x][y]
char map1[105][105];
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};
bool flag;
void dfs (int x, int y, int dir) //dir
{
if (x == ex && y == ey)
{
if (p[x][y] <= k)
flag = true;
return ;
}
//x !=ex && y != ey ，
if ((x !=ex && y != ey && p[x][y] == k)||p[x][y]>k)
return ;
for (int i = 0; i < 4; i++)
{
int tx = x + x_move[i];
int ty = y + y_move[i];
if (tx < 0 || tx >= m|| ty < 0 || ty >= n) //
continue;
//
if (map1[tx][ty] == '*' || p[tx][ty] < p[x][y]) //
continue;
if (dir != -1 && i != dir && p[tx][ty] == p[x][y] )
continue; //
if (dir != -1 && i != dir)
p[tx][ty]=p[x][y]+1; // +1
else p[tx][ty] = p[x][y];
dfs (tx, ty, i);
if (flag) return ;
}
}
int main()
{
int t,i,j,sx,sy; //sx， sy
scanf ("%d", &t);
while (t--)
{
scanf("%d%d",&m,&n);
for(i=0;i<m;i++)
scanf ("%s",map1[i]);
scanf("%d%d%d%d%d",&k,&sy,&sx,&ey,&ex);
sx--,sy--,ex--,ey--; // 0 ， 1
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
p[i][j] = 10005; //
p[sx][sy] = 0; //
flag = false;
dfs (sx, sy, -1); // ， -1
if (flag) puts ("yes");
else puts ("no");
}
return 0;
}
//15MS 284K