HDu 1175 DFSを連続して見る
14782 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1175
問題を解く構想:出発点からDFSを始める.出発点と終点の間は0でしかつながっていないか、直接つながっているかで、このような経路を見つけることができるかどうかを判断します.
View Code
問題を解く構想:出発点からDFSを始める.出発点と終点の間は0でしかつながっていないか、直接つながっているかで、このような経路を見つけることができるかどうかを判断します.
1 #include<cmath>
2 #include<cstdio>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7 #define N 1005
8 #define M 1005
9 int map[N][M],n,m;
10 bool vis[N][M],ok;
11 int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
12 void can(int x,int y,int l1,int l2,int time,int last)//time
13 {
14 int i,xx,yy;
15 if(ok)
16 return;
17 if(time>2)
18 return;
19 for(i=0;i<4&&ok==false;i++)
20 {
21 xx=x+move[i][0];
22 yy=y+move[i][1];
23 if(xx>0&&xx<=n&&yy>0&&yy<=m)
24 {
25 if(xx==l1&&yy==l2)
26 {
27 if(time<2){
28 ok=true;return;
29 }
30 else if(i==last)
31 {
32 ok=true;return;
33 }
34 }
35 if(map[xx][yy]==0&&!vis[xx][yy])
36 {
37 vis[xx][yy]=true;
38 if(i==last)
39 can(xx,yy,l1,l2,time,last);
40 else
41 can(xx,yy,l1,l2,time+1,i);
42 vis[xx][yy]=false;
43 }
44 }
45 }
46 return;
47 }
48 int main()
49 {
50 // freopen("in.in","r",stdin);
51 int k,i,j;
52 while(scanf("%d%d",&n,&m),n+m)
53 {
54 for(i=1;i<=n;i++)
55 for(j=1;j<=m;j++)
56 scanf("%d",&map[i][j]);
57 scanf("%d",&k);
58 int x,y,l1,l2;
59 while(k--)
60 {
61 ok=false;
62 scanf("%d%d%d%d",&x,&y,&l1,&l2);
63 if(map[x][y]!=map[l1][l2])
64 ok=false;
65 else if(map[x][y]==0)
66 ok=false;
67 else
68 {
69 if((((x+1)==l1||(x-1)==l1)&&l2==y)||((y-1)==l2||(y+1)==l2)&&x==l1)
70 ok=true;
71 else
72 {
73 memset(vis,false,sizeof(vis));
74 int tt,rr;
75 for(i=0;i<4&&ok==false;i++)
76 {
77 tt=x+move[i][0];
78 rr=y+move[i][1];
79 if(tt>0&&tt<=n&&rr>0&&rr<=m&&map[tt][rr]==0&&!vis[tt][rr]){
80 vis[tt][rr]=true;
81 can(tt,rr,l1,l2,0,i);//i
82 vis[tt][rr]=false;
83 }
84 }
85 }
86 }
87 if(ok)
88 printf("YES
");
89 else
90 printf("NO
");
91 }
92 }
93 return 0;
94 }View Code