題意：
? ? ?給你一個(gè)n*n的圖，給你驢和老虎的初始坐標(biāo)和方向，已知他們的速度相同，他們走動(dòng)的時(shí)候都是走直線，如果不能走，驢往右拐，老虎往左拐，如果拐了一次還走不了就原地不動(dòng)，問(wèn)他們的最早相遇位置。

思路：

? ? ?直接模擬就行了，我用的是搜索模擬的，不搜索也一樣，把他們到達(dá)每個(gè)格子的時(shí)間都記錄下來(lái)，如果相等或者是A比B大，但是B已經(jīng)到達(dá)終點(diǎn)了，就算相遇，記錄的時(shí)候記得是要最早的那次相遇就行了。

#include<stdio.h> #include<string.h>#define N 1100 + 5 int map_A[N][N] ,map_B[N][N]; int x1 ,y1 ,x2 ,y2 ,n; int dir[4][2] = {0 ,1 ,1 ,0 ,0 ,-1 ,-1 ,0}; bool ok_A(int x ,int y) {if(x <= n && x >= 1 && y <= n && y >= 1 && !map_A[x][y]){x1 = x ,y1 = y;return 1;}return 0; }bool ok_B(int x ,int y) {if(x <= n && x >= 1 && y <= n && y >= 1 && !map_B[x][y]){x2 = x ,y2 = y;return 1;}return 0; }void Dfs_A(int x ,int y ,int t ,int fx) {int nowx = x + dir[fx][0];int nowy = y + dir[fx][1];while(ok_A(nowx ,nowy)){map_A[nowx][nowy] = ++t;nowx += dir[fx][0];nowy += dir[fx][1];}nowx -= dir[fx][0];nowy -= dir[fx][1]; nowx += dir[(fx+1)%4][0];nowy += dir[(fx+1)%4][1];if(ok_A(nowx ,nowy)){ map_A[nowx][nowy] = ++t;Dfs_A(nowx ,nowy ,t ,(fx+1)%4);} } void Dfs_B(int x ,int y ,int t ,int fx) {int nowx = x + dir[fx][0];int nowy = y + dir[fx][1];while(ok_B(nowx ,nowy)){map_B[nowx][nowy] = ++t;nowx += dir[fx][0];nowy += dir[fx][1];}nowx -= dir[fx][0];nowy -= dir[fx][1];nowx += dir[(fx-1+4)%4][0];nowy += dir[(fx-1+4)%4][1];if(ok_B(nowx ,nowy)){map_B[nowx][nowy] = ++t;Dfs_B(nowx ,nowy ,t ,(fx-1+4)%4);} } int main () {int x11 ,y11 ,d11 ,x22 ,y22 ,d22 ,i ,j;while(~scanf("%d" ,&n) && n){scanf("%d %d %d" ,&x11 ,&y11 ,&d11);scanf("%d %d %d" ,&x22 ,&y22 ,&d22);x11 ++ ,y11 ++ ,x22 ++ ,y22 ++;memset(map_A ,0 ,sizeof(map_A));memset(map_B ,0 ,sizeof(map_B));map_A[x11][y11] = 1;x1 = x11 ,y1 = y11;Dfs_A(x11 ,y11 ,1 ,d11);map_B[x22][y22] = 1;x2 = x22 ,y2 = y22;Dfs_B(x22 ,y22 ,1 ,d22);int mk = 0 ,ii ,jj; for(i = 1 ;i <= n;i ++)for(j = 1 ;j <= n;j ++){if(!map_A[i][j] || !map_B[i][j])continue;if(map_A[i][j] == map_B[i][j]) {if(!mk || mk > map_A[i][j]){ii = i ,jj = j ,mk = map_A[i][j];}}if(map_A[i][j] > map_B[i][j] && i == x2 && j == y2){if(!mk || mk > map_A[i][j]){ii = i ,jj = j ,mk = map_A[i][j];}}if(map_A[i][j] < map_B[i][j] && i == x1 && j == y1){if(!mk || mk > map_B[i][j]){ii = i ,jj = j ,mk = map_B[i][j];}}}if(mk) printf("%d %d\n" ,ii - 1,jj - 1);else printf("-1\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4740 不错的简单搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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