Home » C++ » HDU1175 Lianliankan [] [] search pruning

HDU1175 Lianliankan [] [] search pruning

Lianliankan
Time, Limit:, 20000/10000, MS (Java/Others), Memory, Limit:, 65536/32768, K (Java/Others)

Total Submission (s): 26540Accepted, Submission (s): 6590






Problem Description


"Lianliankan" I believe many people have played. Never played also never mind, let me introduce the rules of the game: in a chessboard, put a lot of pieces. If one of the same two pieces by a line together (this line can not pass through other pieces). The number and the turning line of not more than two times, then the two pieces can be deleted on the board. Because I feel shy, not previously played Lianliankan, consult the opinions of the students, can not connect from around the outside of the past, but in fact it is wrong. Now it can only lead to disaster, mistake from the outside, the connection can not be around.

Players click two pieces of chess, trying to eliminate them, and then the background of the game to determine whether the two squares can be removed. Now your task is to write the background program.







Input


Input data from a number of groups, the first row of data there are two positive integers n, m (0 input end
Note: there is no relationship between inquiries, both for the current state,
!






Output


Each set of input data corresponds to one line of output. If it is removed, the output "YES" cannot be output, "NO".







Sample Input


3 4
1234
0000
4321
Four
1134
1124
1133
2124
34
0143
0241
0000
Two
1124
1323
0 0







Sample Output


YES
NO
NO
NO
NO
YES







Author


Lwg






Recommend


We have carefully selected several similar problems for you:11801072101610261010



deep search can be, but I think the use of wide search more realistic, here is a deep search, a simple point.


started writing 7000ms+, and then looked at other people's 0ms...


, then search the Internet, found that you can prune, so I deeply appreciate the power of pruning. Suddenly changed from 7000+ to 90ms, I went to.


this pruning is when you turn the last time, you can directly determine whether the end point and the current point are in a straight line, or, if not, backtrack directly to.


wrote two kinds of pruning here. The second notes are more refined, but they don't seem to have any eggs, or 90ms. really doesn't know how those 0ms are written,.


#include 
#include
Using namespace std;
Int a[1000+100][1000+100];
Bool vis[1000+100][1000+100];
Int, N, m;
Int, x1, Y1, X2, y2;
Bool flag;
Int cnt;
Int dx[]={-1,1,0,0},
Dy[]={0,0, -1,1};
Void DFS (int, x, int, y, int, DIR)
{
If (flag) return;
If (cnt==3)
{
If (x =x2 y =y2! Return!);
/ / this finer than the above phrase pruning didn't seem to be much better
/ / if (dir==0)
{/ /
/ / if (Y =y2 y2} / /
Else / if (dir==1)
{/ /
/ / if (Y =y2 y2>y return ||!);
} / /
Else / if (dir==2)
{/ /
/ / if (x =x2 y2>y return ||!);
} / /
/ / else
{/ /
/ / if (x =x2 y2} / /
}
If (cnt>3) return;
If (x==x2&&y==y2)
{
Flag=1;
Return;
}
If (a[x][y] =-1 return & & dir!);
For (int d=0; d<4; ++d)
{
Int, nx=x+dx[d], ny=y+dy[d];
If (! Vis[nx][ny] & & nx>=1 & & nx<=n & & ny>=1 & & ny<=m)
{
If (D, =dir) cnt++; //change direction
Vis[nx][ny]=1;
DFS (NX, NY, D);
Vis[nx][ny]=0;
If (D, =dir) cnt--;
If (flag) return;
}
}
}
Int main (void)
{
Cin.tie (0); ios:: sync_with_stdio (0);
While (cin>>n>>m, n)
{
Memset (a, 0, sizeof, a);
Memset (VIS, 0, sizeof, VIS);
For (int i=1; i<=n; ++i)
For (int j=1; j<=m; ++j)
Cin>>a[i][j];
Int q;
Cin>>q;
While (q--)
{
Cin>>x1>>y1>>x2>>y2;
Bool fail=0;
If (a[x1][y1] =a[x2][y2] (a[x1][y1] || ||!!! A[x2][y2] //number differ or has zero))
Fail=1;
Flag=0;
Cnt=0;
If (... Fail)
DFS (x1, Y1, -1);
If (flag)
Cout<< "YESn"";
Else
Cout<< "NOn"";
}
}
Return 0;
}
*
34
0143
0241
0000
Ninety-nine
1224
*/




Latest