http://acm.hdu.edu.cn/showproblem.php?pid=1175
X. DFS
http://blog.csdn.net/iaccepted/article/details/24023215
题意很简单，就是我们平时玩的连连看的游戏规则，刚开始用的广搜，刚开始的剪枝不高效导致爆掉队列，使得内存超限，后来发现，bfs先遍历的点不一定是弯数少的点，这样的话如果不专门来更新的话，就会出现运行结果跟搜索顺序有关，是左上右下还是左下右上等等序列。因为至多两个弯，而数据量是1000*1000的，用dfs搜索的时候，只要找到合法解就行，不需要找弯数最少等最优情况，所以只要找到合法解就进行全局标记，这样其他就不需要搜索了，综合的效率其实非常高，大约在o(kn)级别，而且k不很大，具体也不好推算。后来又加了一个剪枝，即当弯数为二时，若此时点的方向不能直接到达目标点就减去此点，很好理解，因为不满足的话到目标点就必须要拐弯，所以弯数就会超过2，但此剪枝的效率并不高，节省大约20mm。
X. BFS
http://www.cppblog.com/mythit/archive/2009/04/29/81497.html?opt=admin
一看题目就知道是用bfs，但是要注意几个问题：bfs是按层次进行搜索，得到的从起点到终点的路径(如果存在的话)是最短的。题目中说这条路径最多只能转向2次，有一些情况可能得到了从起点到终点的路径，但是它的转向次数已经超过的2次，这样这条路径就不符合要求，得重新找一条。一个一般的结论：如果某一点记录的转向次数大于当前路径在该点的转向次数，那么还能从该点再发出一条路径来查找。可以用一个二维数组hash[n][n]来状态判重，这个数组里存的数值就是某条路径在该点的转向次数，if(hash[x][y]>=now.turn) q.push(now)；还有个需要注意的就是能连上的点并没有从图中消失，所以每条查询语句都是独立的。(我把它当成真正的连连看来做，结果WA了10次)
5 const int N = 1001;
6 bool flag;
7 int n,m,sx,sy,ex,ey;
8 int hash[N][N],map[N][N];
9 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
10 struct node{
11 int x,y,turn,d;
12 }start;
13 queue<node> q;
14
15 inline bool in(const node &p){
16 if(p.x<0 || p.y<0 || p.x>=n || p.y>=m)
17 return false;
18 return true;
19 }
20 void bfs(){
21 node now,t;
22 while(!q.empty()){
23 now=q.front(),q.pop();
24 if(now.x==ex && now.y==ey && now.turn<=2){
25 flag=true;
26 return;
27 }
28 for(int i=0;i<4;i++){
29 t.x=now.x+dir[i][0],t.y=now.y+dir[i][1];
30 if(now.d==i)
31 t.turn=now.turn,t.d=now.d;
32 else
33 t.turn=now.turn+1,t.d=i;
34 if(in(t) && (map[t.x][t.y]==0||t.x==ex&&t.y==ey) && hash[t.x][t.y]>=t.turn)
35 hash[t.x][t.y]=t.turn,q.push(t);
36 }
37 }
38 }
39 int main(){
40 int i,j,t;
41 while(scanf("%d %d",&n,&m),n||m){
42 for(i=0;i<n;i++)
43 for(j=0;j<m;j++) scanf("%d",&map[i][j]);
44 scanf("%d",&t);
45 while(t--){
46 scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
47 sx--,sy--,ex--,ey--;
48 if((map[sx][sy]!=map[ex][ey]) || map[sx][sy]==0 || map[ex][ey]==0 || (sx==ex&&sy==ey)){
49 puts("NO");
50 continue;
51 }
52 for(i=0;i<n;i++)
53 for(j=0;j<m;j++) hash[i][j]=11;
54 while(!q.empty()) q.pop();
55 for(i=0;i<4;i++){
56 start.x=sx,start.y=sy,start.turn=0,start.d=i;
57 q.push(start);
58 }
59 flag=false,hash[sx][sy]=0;
60 bfs();
61 puts(flag ? "YES":"NO");
62 }
63 }
64 return 0;
65 }
http://www.wutianqi.com/?p=2640
http://www.cocos.com/doc/tutorial/show?id=1828
http://rayleung.iteye.com/blog/480020
Problem Description
“连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
Input
输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)，分别表示棋盘的行数与列数。在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。
注意：询问之间无先后关系，都是针对当前状态的！
注意：询问之间无先后关系，都是针对当前状态的！
Output
每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。
Sample Input
3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0
Sample Output
YES NO NO NO NO YES
X. DFS
http://blog.csdn.net/iaccepted/article/details/24023215
题意很简单，就是我们平时玩的连连看的游戏规则，刚开始用的广搜，刚开始的剪枝不高效导致爆掉队列，使得内存超限，后来发现，bfs先遍历的点不一定是弯数少的点，这样的话如果不专门来更新的话，就会出现运行结果跟搜索顺序有关，是左上右下还是左下右上等等序列。因为至多两个弯，而数据量是1000*1000的，用dfs搜索的时候，只要找到合法解就行，不需要找弯数最少等最优情况，所以只要找到合法解就进行全局标记，这样其他就不需要搜索了，综合的效率其实非常高，大约在o(kn)级别，而且k不很大，具体也不好推算。后来又加了一个剪枝，即当弯数为二时，若此时点的方向不能直接到达目标点就减去此点，很好理解，因为不满足的话到目标点就必须要拐弯，所以弯数就会超过2，但此剪枝的效率并不高，节省大约20mm。
const int MAX = 1003;
const int dirx[5] = {0,0,1,0,-1};
const int diry[5] = {0,1,0,-1,0};
bool visit[MAX][MAX];
int map[MAX][MAX];
int wan[MAX][MAX];
int n,m,bx,by;
bool mark;
bool yes(int x,int y,int dir){
int dx = bx - x;
int dy = by - y;
if(dx!=0)dx = dx/abs(dx);
if(dy!=0)dy = dy/abs(dy);
if(dx==dirx[dir] && dy==diry[dir])return true;
else return false;
}
void dfs(int x,int y,int cnt,int dir){
int i,tx,ty;
if(mark)return;
if(x<1 || y<1 || x>n || y>m || cnt>2)return;
//注意下面几个剪枝的顺序，顺序搞错了就会出错，因为最后一个元素非0
if(x==bx && y==by){
mark = true;
return;
}
if(cnt==2 && !yes(x,y,dir))return;//这个剪枝不强力，加了此剪枝时间只减少了18ms
if(map[x][y]!=0)return;
if(wan[x][y]!=-1 && wan[x][y]<=cnt)return;
wan[x][y] = cnt;
for(i=1;i<=4;++i){
tx = x + dirx[i];
ty = y + diry[i];
if(dir!=i){
dfs(tx,ty,cnt+1,i);
}else{
dfs(tx,ty,cnt,i);
}
}
}
int main(){
// freopen("in.txt","r",stdin);
int i,j,t,ax,ay;
while(scanf("%d %d",&n,&m)!=EOF){
if(n==0 && m==0)break;
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
scanf("%d",&map[i][j]);
}
}
scanf("%d",&t);
while(t--){
memset(wan,-1,sizeof(wan));
scanf("%d %d %d %d",&ax,&ay,&bx,&by);
mark = false;
if(map[ax][ay]!=map[bx][by] || map[ax][ay]==0){
printf("NO\n");
continue;
}
wan[ax][ay] = 0;
for(i=1;i<=4;++i){
dfs(ax+dirx[i],ay+diry[i],0,i);
}
if(mark){
printf("YES\n");
}else{
printf("NO\n");
}
}
}
return 0;
}
http://www.cnblogs.com/Lee-geeker/p/3234419.html
这题在DFS的同时必须考虑剪枝，，给出三个别人的代码，一个耗时7秒多，一个2秒多，最后一个只有46MS，相差甚大，都是剪枝的功劳。
const int MAX =1002; 4 bool flag = false; 5 bool vist[MAX][MAX]; 6 int s,e,map[MAX][MAX]; 7 int dir[5][3]={{1,0},{0,1},{-1,0},{0,-1}}; 8 void DFS(int x,int y,int cnt,int d) 9 { 10 if(cnt>2||vist[x][y]||flag)return; 11 vist[x][y] = true; 12 for(int i = 0;i < 4;i++) 13 { 14 int a,b,t; 15 a = x + dir[i][0]; 16 b = y + dir[i][1]; 17 if(d!=i) t = cnt +1; 18 else t = cnt; 19 if(a==s&&b==e&&t<=2) 20 {flag = true;return ;} //printf("x-%d y-%d a-%d b-%d\n",x,y,a,b); 21 if(!map[a][b]&&!vist[a][b]) 22 DFS(a,b,t,i); 23 } 24 vist[x][y] = false; 25 } 26 int main() 27 { 28 //freopen("Input.txt","r",stdin); 29 //freopen("Output.txt","w",stdout); 30 int n,m,u,v,q; 31 while(scanf("%d%d",&n,&m),(n||m)) 32 { 33 memset(map,-1,sizeof(map)); 34 for(int i = 1;i <= n;i++) 35 for(int j = 1;j <= m;j++) 36 scanf("%d",&map[i][j]); 37 scanf("%d",&q); 38 while(q--) 39 { 40 scanf("%d%d%d%d",&u,&v,&s,&e); 41 flag = false; 42 memset(vist,false,sizeof(vist)); 43 if(map[u][v]!=map[s][e]||map[u][v]==0); 44 else 45 DFS(u,v,-1,-1); 46 if(flag) 47 puts("YES"); 48 else 49 puts("NO"); 50 } 51 } 52 return 0; 53 }
//【解题思路】：dfs+剪枝。其实没什么好说的，有几个要注意的地方，第一个是判重，第二个是记住最多仅能够进行两次转向。切记，在判断到达目标的时候，需要判断其转向次数是否超过两次，表示个人在此处wa了两次。 纯暴力版过了之后。有一个剪枝是：在转向两次之后，因为不可转向，所以接下来必须与之前的方式保持一致，这个优化减少了5s左右的时间，原先是7000ms，现在是2000ms。
1。首先需要判断给定的俩个棋子是否相同
2。如果给定的坐标没有棋子直接输出NO
3。如果给定的坐标是同一个，也直接输出NO。。不知道测试数据里有没有这么恶心的数据，不过小心为上吧。。
3。本题搜索需要一点方向感。盲目搜索必定超时，因为本题可以进行俩次转向。。所以可以分为三种情况。我用turn来标记转向的次数
turn=0 则直接进行下一步搜索。
turn=1 则需要判断 状态的方向 dir 是否与 需要寻找的棋子位置反向了。。如果反向则放弃搜索、、
turn=2 则判断是否和目标棋子在一条直线上，而且需要判断方向是否一致。。否则放弃搜索。。
int n,m; int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; bool used[1005][1005]; int flag; struct State { int x; int y; int dir; int turn; int step; }; State start; State end; int map[1005][1005]; bool Judge(State t) { if(t.x==end.x&&t.y==end.y) return 1; if(t.turn==0) return 1; if(t.turn==1) { if(t.x>end.x&&t.dir==1) return 0; if(t.y>end.y&&t.dir==3) return 0; if(t.x<end.x&&t.dir==0) return 0; if(t.y<end.y&&t.dir==2) return 0; return 1; } if(t.turn==2) { if(t.x==end.x) { if(t.y>end.y&&t.dir==2) return 1; if(t.y<end.y&&t.dir==3) return 1; } if(t.y==end.y) { if(t.x>end.x&&t.dir==0) return 1; if(t.x<end.x&&t.dir==1) return 1; } return 0; } return 1; } void DFS(State t) { if(flag) return; if(t.turn>2) return; if(t.x==end.x&&t.y==end.y) { flag=1; return; } int x,y; State temp; if(t.step==0) { for(int i=0;i<4;i++) { temp.x=t.x+move[i][0]; temp.y=t.y+move[i][1]; if(temp.x<=0||temp.y<=0||temp.x>n||temp.y>m||used[temp.x][temp.y]==1) continue; temp.dir=i; temp.turn=0; temp.step=t.step+1; if(Judge(temp)==0) continue; used[temp.x][temp.y]=1; DFS(temp); used[temp.x][temp.y]=0; } return; } if(map[t.x][t.y]!=0) return; for(int i=0;i<4;i++) { temp.x=t.x+move[i][0]; temp.y=t.y+move[i][1]; if(temp.x<=0||temp.y<=0||temp.x>n||temp.y>m||used[temp.x][temp.y]==1) continue; if(t.dir!=i) { temp.dir=i; temp.turn=t.turn+1; }else { temp.dir=t.dir; temp.turn=t.turn; } temp.step=1; if(Judge(temp)==0) continue; used[temp.x][temp.y]=1; DFS(temp); used[temp.x][temp.y]=0; } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t; while(scanf("%d %d",&n,&m)) { if(n==0&&m==0) return 0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]); scanf("%d",&t); while(t--) { scanf("%d %d %d %d",&start.x,&start.y,&end.x,&end.y); if(start.x==end.x&&start.y==end.y) { printf("NO\n"); continue; } if(map[start.x][start.y]!=map[end.x][end.y]||map[start.x][start.y]==0||map[end.x][end.y]==0) { printf("NO\n"); continue; } memset(used,0,sizeof(used)); used[start.x][start.y]=1; start.turn=0; start.step=0; flag=0; DFS(start); if(flag) printf("YES\n"); else printf("NO\n"); } } return 0; }
X. BFS
http://www.cppblog.com/mythit/archive/2009/04/29/81497.html?opt=admin
一看题目就知道是用bfs，但是要注意几个问题：bfs是按层次进行搜索，得到的从起点到终点的路径(如果存在的话)是最短的。题目中说这条路径最多只能转向2次，有一些情况可能得到了从起点到终点的路径，但是它的转向次数已经超过的2次，这样这条路径就不符合要求，得重新找一条。一个一般的结论：如果某一点记录的转向次数大于当前路径在该点的转向次数，那么还能从该点再发出一条路径来查找。可以用一个二维数组hash[n][n]来状态判重，这个数组里存的数值就是某条路径在该点的转向次数，if(hash[x][y]>=now.turn) q.push(now)；还有个需要注意的就是能连上的点并没有从图中消失，所以每条查询语句都是独立的。(我把它当成真正的连连看来做，结果WA了10次)
5 const int N = 1001;
6 bool flag;
7 int n,m,sx,sy,ex,ey;
8 int hash[N][N],map[N][N];
9 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
10 struct node{
11 int x,y,turn,d;
12 }start;
13 queue<node> q;
14
15 inline bool in(const node &p){
16 if(p.x<0 || p.y<0 || p.x>=n || p.y>=m)
17 return false;
18 return true;
19 }
20 void bfs(){
21 node now,t;
22 while(!q.empty()){
23 now=q.front(),q.pop();
24 if(now.x==ex && now.y==ey && now.turn<=2){
25 flag=true;
26 return;
27 }
28 for(int i=0;i<4;i++){
29 t.x=now.x+dir[i][0],t.y=now.y+dir[i][1];
30 if(now.d==i)
31 t.turn=now.turn,t.d=now.d;
32 else
33 t.turn=now.turn+1,t.d=i;
34 if(in(t) && (map[t.x][t.y]==0||t.x==ex&&t.y==ey) && hash[t.x][t.y]>=t.turn)
35 hash[t.x][t.y]=t.turn,q.push(t);
36 }
37 }
38 }
39 int main(){
40 int i,j,t;
41 while(scanf("%d %d",&n,&m),n||m){
42 for(i=0;i<n;i++)
43 for(j=0;j<m;j++) scanf("%d",&map[i][j]);
44 scanf("%d",&t);
45 while(t--){
46 scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
47 sx--,sy--,ex--,ey--;
48 if((map[sx][sy]!=map[ex][ey]) || map[sx][sy]==0 || map[ex][ey]==0 || (sx==ex&&sy==ey)){
49 puts("NO");
50 continue;
51 }
52 for(i=0;i<n;i++)
53 for(j=0;j<m;j++) hash[i][j]=11;
54 while(!q.empty()) q.pop();
55 for(i=0;i<4;i++){
56 start.x=sx,start.y=sy,start.turn=0,start.d=i;
57 q.push(start);
58 }
59 flag=false,hash[sx][sy]=0;
60 bfs();
61 puts(flag ? "YES":"NO");
62 }
63 }
64 return 0;
65 }
http://www.wutianqi.com/?p=2640
http://www.cocos.com/doc/tutorial/show?id=1828
http://rayleung.iteye.com/blog/480020
