hdu 1175 連連看

Description

“連連看”相信很多人都玩過。沒玩過也沒關系，下面我給大家介紹一下遊戲規則：在一個棋盤中，放了很多的棋子。如果某兩個相同的棋子，可以通過一條線連起來（這條線不能經過其它棋子），而且線的轉折次數不超過兩次，那麼這兩個棋子就可以在棋盤上消去。不好意思，由于我以前沒有玩過連連看，咨詢了同學的意見，連線不能從外面繞過去的，但事實上這是錯的。現在已經釀成大禍，就隻能将錯就錯了，連線不能從外圍繞過。

玩家滑鼠先後點選兩塊棋子，試圖将他們消去，然後遊戲的背景判斷這兩個方格能不能消去。現在你的任務就是寫這個背景程式。

Input

輸入資料有多組。每組資料的第一行有兩個正整數n,m(0＜n≤100,0＜m≤100),分别表示棋盤的行數與列數。

在接下來的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      

Source

hdu 1175

 #include<iostream>

using namespace std;

int b[1020][1020];

int n, m, q;

bool standard(int c1, int c2, int r)

{

int t;

if(c1>c2)

{

t=c1;

c1=c2;

c2=t;

}

for(int i=c1+1;i<=c2-1;i++)

{

if(b[r][i]!=0)

return false;

}

return true;

}

bool vertical(int r1,int r2, int c)

{

int t;

if(r1>r2)

{

t=r1;r1=r2;r2=t;

}

for(int i=r1+1;i<=r2-1;i++)

{

if(b[i][c]!=0)

return false;

}

return true;

}

bool check(int r1,int c1,int r2,int c2)

{

if(b[r1][c1]==0||b[r2][c2]==0||b[r1][c1]!=b[r2][c2]||r1==r2&&c1==c2)

return false;

for(int i=1;i<=n;i++) //walk 一|__

{

if((i!=c1&&b[r1][i]!=0)||(i!=c2&&b[r2][i]!=0))

continue;

if(standard(i,c1,r1)&&vertical(r1,r2,i)&&standard(i,c2,r2))

return true;

}

for(int i=1;i<=m;i++) //walk |_|

{

if((i!=r1&&b[i][c1]!=0)||(i!=r2&&b[i][c2]!=0))

continue;

if(vertical(i,r1,c1)&&standard(c1,c2,i)&&vertical(i,r2,c2))

return true;

}

return false;

}

int main()

{

int x1, y1, x2, y2, i, j;

while( cin>>n>>m&&(n||m) )

{

for(i=1;i<=n;++i)

{

for(j=1;j<=m;++j)

scanf("%d ", &b[i][j]);

}

scanf("%d", &q);

while( q-- )

{

cin>>x1>>y1>>x2>>y2;

if( check(x1,y1,x2,y2) )

cout<<"YES/n";

else

cout<<"NO/n";

}

}

return 0;

}

#include <iostream>

#include <queue>

using namespace std;

const int N = 1001;

bool flag;

int n,m,sx,sy,ex,ey;

int hash[N][N],map[N][N];

int dir[4][2]={​{1,0},{0,1},{-1,0},{0,-1}};

struct node{

int x,y,turn,d;

}start;

queue<node> q;

inline bool in(const node &p){

if(p.x<0 || p.y<0 || p.x>=n || p.y>=m)

return false;

return true;

}

void bfs(){

node now,t;

while(!q.empty()){

now=q.front(),q.pop();

if(now.x==ex && now.y==ey && now.turn<=2){

flag=true;

return;

}

for(int i=0;i<4;i++){

t.x=now.x+dir[i][0],t.y=now.y+dir[i][1];

if(now.d==i)

t.turn=now.turn,t.d=now.d;

else

t.turn=now.turn+1,t.d=i;

if(in(t) && (map[t.x][t.y]==0||t.x==ex&&t.y==ey) && hash[t.x][t.y]>=t.turn)

hash[t.x][t.y]=t.turn,q.push(t);

}

}

} int main(){

int i,j,t;

while(scanf("%d %d",&n,&m),n||m){

for(i=0;i<n;i++)

for(j=0;j<m;j++) scanf("%d",&map[i][j]);

scanf("%d",&t);

while(t--){

scanf("%d %d %d %d",&sx,&sy,&ex,&ey);

sx--,sy--,ex--,ey--;

if((map[sx][sy]!=map[ex][ey]) || map[sx][sy]==0 || map[ex][ey]==0 || (sx==ex&&sy==ey)){

puts("NO");

continue;

}

for(i=0;i<n;i++)

for(j=0;j<m;j++) hash[i][j]=11;

while(!q.empty()) q.pop();

for(i=0;i<4;i++){

start.x=sx,start.y=sy,start.turn=0,start.d=i;

q.push(start);

}

flag=false,hash[sx][sy]=0;

bfs();

puts(flag ? "YES":"NO");

}

}

return 0;

}