hdoj搜索题集

n久没刷题了,感觉水平退化太多了。。今天开始刷题。
把hdoj以前没做的搜索题做一下
hdu1072 简单题
我的思路:出发点和可重置时间的点没有必要访问两次,其他点可以重复访问。这样不会导致bfs一直进行下去。
其他思路:对于这种点可以重复访问的题,bfs入队时不仅要考虑坐标,还要考虑剩余时间,如果同一个点第二次入队时剩余时间比第一次大于或等于,那么不需要入队,没有意义。

#include<stdio.h>
#include<string.h>
const int maxq=1000000;
int n,m;
int map[9][9];
int vis[9][9];
typedef struct Node{
    int x,y,t,step;
}Node;
Node q[maxq];
int iq;
int dirx[]={0,1,-1,0,0};
int diry[]={0,0,0,1,-1};
int sx,sy,tx,ty,x,y,tt,step;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=sx;q[iq].y=sy;q[iq].t=6;q[iq].step=0;
    iq++;vis[sx][sy]=1;
    for(i=0;i<=iq-1;i++)
    {
        x=q[i].x;y=q[i].y;tt=q[i].t;step=q[i].step;
        if(tt==1) continue;
        for(j=1;j<=4;j++)
        {
            int u=x+dirx[j],v=y+diry[j];
            if(map[u][v]==3) return step+1;
            if(!judge(u,v) || vis[u][v] || map[u][v]==0) continue;
            if(map[u][v]==4) vis[u][v]=1;
            q[iq].x=u;q[iq].y=v;q[iq].t=tt-1;q[iq].step=step+1;
            if(map[u][v]==4) q[iq].t=6;
            iq++;
        }
    }
    return -1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==2) sx=i,sy=j;
                if(map[i][j]==3) tx=i,ty=j;
            }
        printf("%d\n",bfs());
    }
    return 0;
}

hdu1026 简单题
如果答案是1 second,仍然输出1 seconds哦

#include<stdio.h>
#include<string.h>
const int maxq=100000+10;
int n,m;
char map[110][110];
bool vis[110][110];
typedef struct Node{
    int x,y,t,tt;
    int pre;
}Node;
Node q[maxq];
int iq;
int a[]={0,1,-1,0,0};
int b[]={0,0,0,1,-1};
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=1;q[iq].y=1;q[iq].t=0;q[iq].pre=-1;
    iq++;
    vis[1][1]=1;
    for(i=0;i<=iq-1;i++)
    {
        int x=q[i].x,y=q[i].y,t=q[i].t,tt=q[i].tt;
        if(x==n && y==m)
        {
            if('1'<=map[n][m] && map[n][m]<='9')
            {
                if(!tt) return i;
            }
            else return i;
        }
        if('1'<=map[x][y] && map[x][y]<='9' && tt)
        {
            q[iq].x=x;q[iq].y=y;q[iq].t=t+1;q[iq].tt=tt-1;
            q[iq++].pre=i;
            continue;
        }
        for(j=1;j<=4;j++)
        {
            int u=x+a[j],v=y+b[j];
            if(!judge(u,v) || vis[u][v] || map[u][v]=='X') continue;
            q[iq].x=u;q[iq].y=v;q[iq].t=t+1;q[iq].tt=map[u][v]-'0';
            q[iq++].pre=i;
            vis[u][v]=1;
        }
    }
    return -1;
}
void dfs(int cur)
{
    int x=q[cur].x,y=q[cur].y,t=q[cur].t,pre=q[cur].pre;
    int px=q[pre].x,py=q[pre].y;
    if(px==1 && py==1)
    {
        printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
        return;
    }
    dfs(pre);
    if(px==x && py==y) printf("%ds:FIGHT AT (%d,%d)\n",t,x-1,y-1);
    else printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                scanf("%c",&map[i][j]);
            getchar();
        }
        int ans=bfs();
        if(ans==-1) {printf("God please help our poor hero.\nFINISH\n");continue;}
        printf("It takes %d seconds to reach the target position, let me show you the way.\n",q[ans].t);
        dfs(ans);
        printf("FINISH\n");

    }

    return 0;
}

cf375D Tree and Queries

昨天学了莫队算法,发现真的是很神奇,特别是简化版的,按sqrt(n)分块的算法,非常好写。这道题是佳神推荐的,发现确实很好,写下题解,大牛请直接关闭本页。。
题意:题目的意思是给你一棵树,每个节点都有一个正整数值。然后给你m个询问,每次询问你一棵子树中出现次数至少为kj次的数有多少个。题目中所有数都是<=10^5
思路:这题其实是前面写的树那题和分块那题的结合。首先dfs这棵树,得到dfs序。
于是问题转化为:给出一个长为n的序列,m个询问,每次询问[l,r]上有多少个数出现次数至少为qi次
这个问题可以这样:用一个数组cn[i],表示数i出现的次数。再用一个树状数组cc[],其中第i个元素表示出现次数为i次的数有几个。然后就是前面所讲的分块算法了,这在《莫队算法相关》这篇文章里讲过了。每次单步转移(也就是类似[l,r]->[l,r+1]的转移),需要更新cn[],时间是O(1),更新cc[],时间O(lgn).求解时计算getsum(n)-getsum(qi-1),时间为O(lgn).这样复杂度是O((n^1.5)lgn),n=1e5.算了一下大概在5*10^8左右。开始用线段树出现次数为x的数的个数,结果TLE,改成树状数组就过了,不过应该是数据不卡O((n^1.5)lgn)的原因,因为正解貌似是O(n^1.5)的。。待进一步思考
ps:del和insert的时候,少写了if,导致有时候一个数删去之后出现了0次,这时候对出现0次的数的个数+1,结果就出错了。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=1e5+5;
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[maxn*2];
int head[maxn],cnt;
bool visit[maxn];
int n,m,num;
int c[maxn],d[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
typedef struct Node{
    int begin,end;
}Node;
Node node[maxn];
void dfs(int cur)
{
    visit[cur]=1;
    node[cur].begin=(++num);
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);

    }
    node[cur].end=num;
    return;
}
typedef struct Q{
    int l,r,id,count,g;
}Q;
Q q[maxn];
int cn[maxn],ans[maxn];
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
/**
int sum[maxn<<2];
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int pos,int v)
{
    if(l==r)
    {
        sum[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(lson,l,m,pos,v);
    else update(rson,m+1,r,pos,v);
    pushup(id);
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R) return sum[id];
    int m=(l+r)/2;
    int ret=0;
    if(L<=m) ret+=query(lson,l,m,L,R);
    if(R>m) ret+=query(rson,m+1,r,L,R);
    return ret;
}
**/
//树状数组部分
int cc[maxn];
int lowbit(int x)
{
	return x & -x;
}
void add2(int id,int x)
{
	for(int i=id;i<=n;i+=lowbit(i))
		cc[i]+=x;
	return;
}
int getsum(int x)
{
	int sum=0;
	for(int i=x;i>=1;i-=lowbit(i))
		sum+=cc[i];
	return sum;
}
//区间询问转移
void del(int x)
{
    if(cn[d[x]]) {add2(cn[d[x]],-1);cn[d[x]]--;}

    if(cn[d[x]]) add2(cn[d[x]],1);
}
void insert(int x)
{
    if(cn[d[x]]) add2(cn[d[x]],-1);
    cn[d[x]]++;
    if(cn[d[x]]) add2(cn[d[x]],1);
}

void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(cn,0,sizeof(cn));
        //memset(sum,0,sizeof(sum));
        memset(cc,0,sizeof(cc));
        for(i=1;i<=n;i++) scan(c[i]);
        for(i=1;i<=n-1;i++) {scan(a);scan(b);add(a,b);}
        dfs(1);
        for(i=1;i<=n;i++) d[node[i].begin]=c[i];
        int x,y;
        int len=(int)sqrt(n*1.0);
        for(i=1;i<=m;i++)
        {
            scan(x);scan(y);
            q[i].l=node[x].begin;
            q[i].r=node[x].end;
            q[i].id=i;
            q[i].count=y;
            q[i].g=q[i].l/len+1;
        }
        sort(q+1,q+1+m,cmp);
        int curl=0,curr=0;
        for(i=1;i<=m;i++)
        {
            int l=q[i].l,r=q[i].r;
            while(curr<r)
            {
                curr++;
                insert(curr);
            }
            while(curr>r)
            {
                del(curr);
                curr--;
            }
            while(curl<l)
            {
                if(curl) del(curl);
                curl++;
            }
            while(curl>l)
            {
                curl--;
                insert(curl);
            }
            if(q[i].count>n) ans[q[i].id]=0;
            else ans[q[i].id]=getsum(n)-getsum(q[i].count-1);
        }
        for(i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}
/*
10 1
82 48 59 48 32 83 34 46 47 79
2 1
3 1
4 3
5 4
6 1
7 2
8 3
9 2
10 2
4 1
*/

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15   Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给你一棵N个节点的树,其中1为根节点,每个节点有权值。一开始所有节点的权值均为0。现在我们要进行M次操作。
  一共有以下两种操作:
  1)1 u d 节点1到节点u的最短路径上的所有的节点(包括1,u)的权值增加d(1<=d<=300)
  2)2 u 查询节点u的权值

Input

  多组测试数据
  每组测试数据第一行有两个数N,M (1<=N,M<=60000)
  接下来N-1行 每行有两个数u,v (1<=u,v<=N且u!=v)表示节点u和节点v之间有一条边
  接下来M行,即M次操作,含义见题目描述

Output

  对于每个操作2,请输出u的权值

Sample Input

3 4
1 2
1 3
1 2 3
2 1
2 2
2 3

Sample Output

3
3
0

Source

test

昨天校赛,这题没想到思路,想到就很简单了。。这题很有意思
思路:如果给某个点加上一个值,从这个点到根的结点都要加上这个值,这样暴力肯定不行。以前做过把树求出dfs序,转化成线段树的题,但是那是对某棵子树的结点都加上一个值,那么这题如果dfs序的话,每次操作要加的那些结点在线段树中时不连续的,怎么解决呢
其实可以这样做,每次操作只修改该点的值,最后求点u的值,只要对以u为根的子树对应的区间求和就行了。。。
当然也可以用树状数组,我比较习惯线段树,虽然慢一些。。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=6e4+5;
typedef struct Edge{
    int to,next;
}Edge;
typedef struct Node{
    int begin,end;
}Node;
Edge edge[2*maxn];
Node node[maxn];
int head[maxn],cnt;

int sum[maxn<<2];
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int pos,int v)
{
    if(l==r)
    {
        sum[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(lson,l,m,pos,v);
    else update(rson,m+1,r,pos,v);
    pushup(id);
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R)
    {
        return sum[id];
    }
    int m=(l+r)/2;
    int ret=0;
    if(L<=m) ret+=query(lson,l,m,L,R);
    if(R>m) ret+=query(rson,m+1,r,L,R);
    return ret;
}
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
}
int n,m,num;
bool visit[maxn];
void dfs(int cur)
{
    visit[cur]=1;
    node[cur].begin=(++num);
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);
    }
    node[cur].end=num;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        int u,v;
        cnt=0;num=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        dfs(1);
        int c,x,d;
        for(i=1;i<=m;i++)
        {
            scanf("%d",&c);
            if(c==1)
            {
                scanf("%d%d",&x,&d);
                update(1,1,n,node[x].begin,d);
            }
            if(c==2)
            {
                scanf("%d",&x);
                printf("%d\n",query(1,1,n,node[x].begin,node[x].end));
            }
        }

    }



    return 0;
}

zoj 3761 Easy billiards dfs树

这题如果想到的话,写起来很简单。。
题意:无限大的二维坐标系中有n(0<=n<=2000)个球,可以用一个球沿与x坐标轴或y坐标轴平行的方向打球,如果球A碰到球B,那么球A停在球B的地方,球B以与A相同的方向前进,如果B运动的方向前方没有球了,那么判定球B出局,否则球B会撞到球C,以此类推,但是一个球不能直接出局,它必须是被某个球撞击后出局。
思路:把“相邻的球”(即可以直接撞击的球)连边,可以发现,同一个连通快中的球最后只会剩一个,,所以建图后dfs之,形成dfs树,为了保证一个连通块中的点撞到只剩一个,所以只要从子节点撞向父节点即可(比如,(0,0)、(1,0)、(0,1)三个点,dfs之后(0,0)是父节点,另两个是子节点,如果这时从(0,0)撞向(1,0)或(0,1)就会出错)
代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef struct Edge{
    int to;
    int next;
}Edge;
typedef struct Point{
    int x,y;
    int num;
}Point;
Point p[2010];
Edge edge[8000+10];
int head[2010],cnt;
int x[2010],y[2010];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int ansx[2010],ansy[2010];
char dir[2010][10];
int num;
bool visit[2010];
void dfs(int cur)
{
    visit[cur]=1;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);
        ansx[++num]=x[v],ansy[num]=y[v];
        if(x[v]==x[cur])
        {
            if(y[v]>y[cur]) strcpy(dir[num],"DOWN");
            else strcpy(dir[num],"UP");
        }
        else if(y[v]==y[cur])
        {
            if(x[v]>x[cur]) strcpy(dir[num],"LEFT");
            else strcpy(dir[num],"RIGHT");
        }
    }
    return;
}
bool cmp1(Point a,Point b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
bool cmp2(Point a,Point b)
{
    if(a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            p[i].x=x[i];p[i].y=y[i];p[i].num=i;
        }
        sort(p+1,p+1+n,cmp1);
        for(i=2;i<=n;i++)
        {
            if(p[i].x==p[i-1].x) add(p[i-1].num,p[i].num);
        }
        sort(p+1,p+1+n,cmp2);
        for(i=2;i<=n;i++)
        {
            if(p[i].y==p[i-1].y) add(p[i-1].num,p[i].num);
        }
        memset(visit,0,sizeof(visit));
        for(i=1;i<=n;i++)
        {
            if(visit[i]) continue;
            dfs(i);
        }
        printf("%d\n",n-num);
        for(i=1;i<=num;i++) printf("(%d, %d) %s\n",ansx[i],ansy[i],dir[i]);
    }
    return 0;
}

hdoj1258

http://acm.hdu.edu.cn/showproblem.php?pid=1258
本题爆搜~,关键是如何防止重复。
其实一个if语句即可:

if(!visit[j-1] && a[j]==a[j-1])
{
   ;               
 }
else
{

}

在要选择a[j]时visit[j-1]==0说明两者之间不是同一方案的前后继关系,若此时a[j]==a[j-1],则a[j]不必考虑。(假设a[j-3]+a[j-1]=t,a[j-1]==a[j],那么显然a[j-3]+a[j]=t的方案和前者重复,不必考虑)
如果不加!visit[j-1]会怎样?
如果不加,可能会造成漏选方案。
例如:t=4;a[j]=1,a[j+1]=1;
2+1+1=4
显然,第2个1是无法选上的,因为a[j]==a[j-1].但其实visit[j-1]==1,所以a[j-1]和a[j]不是并列关系,也就是这两个1必须看成不同的,它们是同一种方案的前后继关系。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int sum=0,n,t;
int visit[13];
int a[13];
int queue[14];
int iq=0;
bool flag=false;
void dfs(int i)
{
	visit[i]=1;
	int j,k;
	if(sum==t)
	{
		flag=true;
		printf("%d",queue[0]);
		for(k=1;k<=iq-1;k++)
			printf("+%d",queue[k]);
		printf("\n");
		return;
	
	}
	for(j=i+1;j<=n;j++)
	{
		if(sum+a[j]<=t && !visit[j])
		    if(!visit[j-1] && a[j]==a[j-1])
		    {
               ;               
                           
            }
            else
            {
                
    			queue[iq++]=a[j];
    			sum+=a[j];
    			dfs(j);
    			visit[j]=0;
    			sum-=a[j];
    			iq--;
    		}
	
	}

return;
}
int main()
{
	int i;
	scanf("%d %d",&t,&n);
	while(n!=0)
	{
		iq=0;
		flag=false;
		sum=0;
		memset(queue,0,sizeof(queue));
		memset(visit,0,sizeof(visit));
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		printf("Sums of %d:\n",t);
		dfs(0);
		if(!flag)
			printf("NONE\n");
		scanf("%d %d",&t,&n);
	}
//system("pause");
return 0;
}

hdoj1010

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1010
这道题作为我初学dfs,记一下,虽然很早就看过dfs算法,但是一直没用它做过题,感觉对它的认识停留在表面。所以接下来要多做搜索题。
先记录些本菜鸟的体会:
1.基于dfs的遍历(如图的dfs遍历),也就是访问完一个节点(指对该点相邻状态均已dfs)回溯到搜索树的上一层时,如果不将该节点改回未访问,则只能遍历所有状态仅一次。
2.要尝试所有路径,则必须在回溯时,重新修改访问情况(修改visit数组)
3.在dfs时,可以为dfs增加全局变量depth来记录当前dfs深度(反映到具体的迷宫问题中,就是走了几步)
4.dfs解决的是从起始状态到目标状态是否有可达路径,路径是什么
5.bfs则解决从起始状态到目标状态最短路径是什么
对于这道题,首先确定要用dfs。用bfs是思想性错误,因为题目要求是在t秒时正好到达出口(因为出口只在t秒时打开)
下面是代码:(注意:1.要剪枝;2.我的程序在所有状态之外加了一层初始化为已访问的状态,这样就不必判边界了,并且墙壁也可以看成已访问的状态,不用分离出来特意判断)

#include<stdio.h>
#include<stdlib.h>
bool visit[8][8];
char maze[8][8];
int depth=-1;
int a[5],b[5];
bool flag;
void dfs(int x,int y,int t)
{
	int i;
	visit[x][y]=true;
	depth++;
	if(maze[x][y]=='D'  && depth==t) {flag=true;return;}//开始没有加return,找到答案后仍然向下搜索,直到遍历整个状态空间(也就是整个迷宫)。结果984MS,改了之后406MS
	for(i=1;i<=4;i++)
	{
		if(visit[x+a[i]][y+b[i]]==false && !flag)//该点四周有未访问的点且现在未找到答案,则递归访问。
			dfs(x+a[i],y+b[i],t);
		else if(flag)//已经找到答案,不用再尝试其他方向,不断向前回溯,此时visit标志没有改回false,也就是说符合答案的路径各点标为了true
			return;
	}
depth--;//程序执行到这里说明该点四周的点均已访问,无法继续遍历,而且未找到答案,此时该点重新标为false,回到上一层,尝试其他方向的点
visit[x][y]=false;
return;
}
int main()
{
	int n,m,t;
	a[1]=-1;b[1]=0;
	a[2]=0;b[2]=-1;
	a[3]=1;b[3]=0;
	a[4]=0;b[4]=1;
	scanf("%d%d%d",&n,&m,&t);
	while(n!=0||m!=0||t!=0)
	{
		getchar();
		int beginx,beginy,endx,endy,i,j;
		flag=false;
		depth=-1;
		for(i=0;i<=n+1;i++)
			for(j=0;j<=m+1;j++)
				visit[i][j]=true;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%c",&maze[i][j]);
				if(maze[i][j]=='S')
				{
					beginx=i;
					beginy=j;
				}
				if(maze[i][j]=='D')
				{
					endx=i;
					endy=j;
				}
				if(maze[i][j]!='X')
					visit[i][j]=false;
			}
			getchar();
		}
		if(((beginx+beginy)%2!=(endx+endy)%2)&&(t%2==0))
		{
			printf("NO\n");
			scanf("%d%d%d",&n,&m,&t);
			continue;
		}
		if(((beginx+beginy)%2==(endx+endy)%2)&&(t%2!=0))
		{
			printf("NO\n");
			scanf("%d%d%d",&n,&m,&t);
			continue;
		}
		dfs(beginx,beginy,t);
		if(flag==true)
			printf("YES\n");
		else
			printf("NO\n");
		scanf("%d%d%d",&n,&m,&t);
	}
return 0;
}

奇偶剪枝:如果起点横纵坐标和与终点坐标和奇偶性不同,则说明要走奇数步,如果要求走t步,t为偶数,则肯定不可能有答案;反之亦然。
开始没剪枝,果断TLE。。剪枝后984MS,进一步修改后406MS.

图的dfs和bfs(基于链式前向星)

看了半天,,总算是对链式前向星了解更深些了,其实就是一种邻接顺序表(邻接表的顺序实现)
图的dfs

bool visit[1000];
void dfs(int x)
{
	visit[x]=true;
	visit x;
	for(k=head[x];k!=-1;k=edge[k].next)
	{
		if(!visit[edge[k].to])
			dfs(edge[k].to);
	}
}

图的bfs

bool visit[1000];
int queue[maxn];//maxn  顶点数
int indegree[maxm];//maxm  弧数,在链式前向星建图时赋值
void bfs(int x)
{
	int iq=0,k;
	queue[iq++]=x;
	visit[x]=true;
	for(i=0;i<=iq-1;i++)
		for(k=head[queue[i]];k!=-1;k=edge[k].next)
		{
			if(!visit[edge[k].to])
			{
				queue[iq++]=edge[k].to;
				visit[edge[k].to]=true;
			}
		}
}
//最终的队列queue就是bfs序列