hdu 4740 （一步一步模拟就好了）考查耐心与细心

灰太狼 2022-09-18 07:53 153阅读 0赞

[http://acm.hdu.edu.cn/showproblem.php?pid=4740][http_acm.hdu.edu.cn_showproblem.php_pid_4740]

网络赛时这道题没做出来，一直Runtime Error(ACCESS\_VIOLATION)，还不心不够静，心态啊！

/***************************
    # 
     1. a[n][n] 代表矩阵；初始为0 
     2. tiger和donkey 同时从起点运动，dfs参数  ： 首先两个坐标（4个参数），表示位置
                                                    两个状态 ，表示tiger和donkey的运动是否，初始1；代表运动
                                      dfs结束条件 ： 都停止（状态都是0） || 相遇（两个坐标相同） 
        
    # 2013-11-12 17:33:16 
    # Time: 31MS   Memory: 8384K
    # Author: zyh
    ***************************/ 
    
    #define N 1020
    
    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>
    
    using namespace std;
    int dir[4][2]={0,1,1,0,0,-1,-1,0};
    int n,flag,vt[N][N],vd[N][N];
    
    void dfs(int tx,int ty,int tdir,bool ts,int dx,int dy,int ddir,bool ds)
    {
    //	printf("%d,%d,%d,%d,%d,%d,%d,%d\n",tx,ty,tdir,ts,dx,dy,ddir,ds);
    	if(tx==dx && ty==dy ){
    		printf("%d %d\n",tx,ty);
    		flag = 1;
    		return;
    	}
    	int ntx = tx,nty = ty,ndx = dx,ndy = dy;
    	//分情况：1.都不能动，结束， 1.都能运动；2.tiger动donkey不动，3.donkey动tiger不动 
    	if(!ts && !ds) return;
    	vt[tx][ty] = vd[dx][dy] = 1 ; 
    	if(ts){
    		if(tx+dir[tdir][0] >=n || ty +dir[tdir][1]>=n //！！！第一次RE是忘了写 <0 的情况了 
    		|| tx+dir[tdir][0] <0 || ty +dir[tdir][1]<0
    		|| vt[tx+dir[tdir][0]][ty +dir[tdir][1]] )//该调头了 
    			tdir = tdir-1<0 ? 3 : tdir-1;	
    		
    		if(tx+dir[tdir][0] >=n || ty +dir[tdir][1]>=n //！！！第二次RE忘了写这里越界的情况了 ！！！ 
    		|| tx+dir[tdir][0] <0 || ty +dir[tdir][1]<0
    		|| vt[tx+dir[tdir][0]][ty +dir[tdir][1]] ) 	ts = 0;//掉头后依然不能继续走，则停止 
    		else ntx = tx+dir[tdir][0],nty = ty +dir[tdir][1];
    	}
    	if(ds){
    		if(dx+dir[ddir][0] >=n || dy +dir[ddir][1]>=n
    		|| dx+dir[ddir][0] <0 || dy +dir[ddir][1]<0
    		|| vd[dx+dir[ddir][0]][dy +dir[ddir][1]] )//该调头了 
    			ddir = ddir+1>3 ? 0 : ddir+1;	
    		
    		if(dx+dir[ddir][0] >=n || dy +dir[ddir][1]>=n 
    		|| dx+dir[ddir][0] <0 || dy +dir[ddir][1]<0
    		|| vd[dx+dir[ddir][0]][dy +dir[ddir][1]] ) ds = 0;//掉头后依然不能继续走，则停止 
    		else ndx = dx+dir[ddir][0],ndy = dy +dir[ddir][1];
    	}
    	dfs(ntx,nty,tdir,ts,ndx,ndy,ddir,ds); //！！！第三次RE 是这里传递参数忘了改了 ！！！ 
    	
    } 
    
    
    int main()
    {
    	int tx,ty,tdir,dx,dy,ddir;
    	while(~scanf("%d",&n),n){
    		scanf("%d%d%d%d%d%d",&dx,&dy,&ddir,&tx,&ty,&tdir);
    		memset(vt,0,sizeof(vt));
    		memset(vd,0,sizeof(vd));
    		flag=0;
    		dfs(  tx,  ty,  tdir,1,  dx,  dy,  ddir,  1);
    		if(!flag) puts("-1");
    	}
    	return 0; 
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_4740]: http://acm.hdu.edu.cn/showproblem.php?pid=4740