其实到现在也不是太明白,看了解题报告敲的。。。。。。。。。。
/* ID: yueqiq PROG: numtri LANG: C++ */ #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) const int maxn = 1001; const int INF = 1111; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; const double pi = acos(-1.0); using namespace std; int N,M,sx,sy,ex,ey; int Map[maxn][maxn]; int vis[maxn][maxn]; struct node{ int x,y,dir,times; }; bool bfs(){ node k,tmp; //vis[sx][sy]=0; tmp.x=sx; tmp.y=sy; tmp.dir=-1; tmp.times=0; queue<node> q; q.push(tmp); while(!q.empty()){ tmp=q.front(); q.pop(); if(tmp.x==ex && tmp.y==ey) return true; FF(i,4){ k.x=tmp.x+dx[i]; k.y=tmp.y+dy[i]; k.times=tmp.times; k.dir=tmp.dir; if(k.x<1 || k.y<1 ||k.x>N ||k.y>M) continue; //if(i-tmp.dir==-2 || i-tmp.dir==2) continue; if(i!=tmp.dir) k.times++; if(tmp.dir==-1) k.times=0; if(Map[k.x][k.y]!=0){ if(k.x==ex && k.y==ey && k.times<=2) return true; continue; } if(k.times>2) continue; k.dir=i; if(k.times>vis[k.x][k.y]) continue; //printf("show k.x=%d k.y=%d k.times=%d k.dir=%d\n",k.x,k.y,k.times,k.dir); vis[k.x][k.y]=k.times; q.push(k); } } return false; } int main() { while(~scanf("%d%d",&N,&M) && N && M){ FOR(i,1,N) FOR(j,1,M){ SD(Map[i][j]); } int q;SD(q); FOR(i,1,q){ SD(sx);SD(sy);SD(ex);SD(ey); if(Map[sx][sy]!=Map[ex][ey]||!Map[sx][sy]||!Map[ex][ey]){ puts("NO");continue; } SET(vis,INF); printf("%s\n",bfs()?"YES":"NO"); } } return 0; }