给你一个n*n的图，给你驴和老虎的初始坐标和方向，已知他们的速度相同，他们走动的时候都是走直线，如果不能走，驴往右拐，老虎往左拐，如果拐了一次还走不了就原地不动，问他们的最早相遇位置。
思路：
直接模拟就行了，我用的是搜索模拟的，不搜索也一样，把他们到达每个格子的时间都记录下来，如果相等或者是A比B大，但是B已经到达终点了，就算相遇，记录的时候记得是要最早的那次相遇就行了。
#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 " ,ii - 1,jj - 1); else printf("-1 "); } return 0; }