Description

可憐的公主在一次次被魔王擄走一次次被騎士們救回來之后，而今，不幸的她再一次面臨生命的考驗。魔王已經(jīng)發(fā)出消息說將在T時刻吃掉公主，因為他聽信謠言說吃公主的肉也能長生不老。年邁的國王正是心急如焚，告招天下勇士來拯救公主。不過公主早已習(xí)以為常，她深信智勇的騎士LJ肯定能將她救出。?
現(xiàn)據(jù)密探所報，公主被關(guān)在一個兩層的迷宮里，迷宮的入口是S（0，0，0），公主的位置用P表示，時空傳輸機用#表示，墻用*表示，平地用.表示。騎士們一進入時空傳輸機就會被轉(zhuǎn)到另一層的相對位置，但如果被轉(zhuǎn)到的位置是墻的話，那騎士們就會被撞死。騎士們在一層中只能前后左右移動，每移動一格花1時刻。層間的移動只能通過時空傳輸機，且不需要任何時間。

Input

輸入的第一行C表示共有C個測試數(shù)據(jù)，每個測試數(shù)據(jù)的前一行有三個整數(shù)N，M，T。 N，M迷宮的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宮的第一層的布置情況，后N*M表示迷宮第二層的布置情況。

Output

如果騎士們能夠在T時刻能找到公主就輸出“YES”，否則輸出“NO”。

Sample Input

1 5 5 14 S*#*. .#... ..... ****. ...#. ..*.P #.*.. ***.. ...*. *.#..

Sample Output

YES dfs #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,t,p; char map[4][20][20]; int v[3][20][20]; int yi[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; void dfs(int x,int y,int k,int time) {if (time>t||p==1) return ;if (map[k%2][x][y]=='P') {p=1;return ;}int i,rx,ry,a;for (i=0;i<4;i++){a=0;rx=x+yi[i][0];ry=y+yi[i][1];if (map[k%2][rx][ry]=='#') a=1;if (map[(k+a)%2][rx][ry]=='#') continue;if (rx>=0&&rx<n&&ry>=0&&ry<m&&map[(k+a)%2][rx][ry]!='*'&&!v[(k+a)%2][rx][ry]){v[(k+a)%2][rx][ry]=1;dfs(rx,ry,k+a,time+1);v[(k+a)%2][rx][ry]=0;}} } int main() {int c,i,j,k;scanf("%d",&c);while (c--){scanf("%d%d%d",&n,&m,&t);for (k=0;k<2;k++)for (i=0;i<n;i++)for (j=0;j<m;j++) scanf(" %c",&map[k][i][j]);p=0;memset(v,0,sizeof(v));map[0][0][0]='*';dfs(0,0,0,0);if (p) printf("YES\n");else printf("NO\n");}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/pblr/p/4698620.html

總結(jié)

以上是生活随笔為你收集整理的HDU-2102 A计划 dfs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。