HDOJ 1175ワイド検索BFS基礎入門問題(詳細コメント付きコード)

5195 ワード

ワイド検索

しきりに見る
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 37107 Accepted Submission(s): 9176
Problem Description
「連見」は多くの人が遊んだことがあると信じています.遊んだことがなくても大丈夫です.次はゲームのルールを紹介します.碁盤の中に、たくさんの駒が置いてあります.もしある2つの同じ駒が、1本の線でつながっていて(この線は他の駒を通ることができません)、しかも線の転換回数が2回を超えなければ、この2つの駒は碁盤の上で消すことができます.申し訳ありませんが、私は以前游んだことがないので、友达の意見を聞いて、外から迂回することはできませんが、実はこれは間違っています.今はすでに大きな災いになって、間違いを間違えるしかなくて、線は外周から迂回することができません.
プレイヤーのマウスは前後して2つの駒をクリックして、彼らを消そうとして、それからゲームのバックグラウンドはこの2つの格子が消せるかどうかを判断します.今あなたの任務はこのバックグラウンドプログラムを書くことです.

Input
入力データは複数組あります.各グループのデータの最初の行には2つの正の整数nがあり、m(0注意:問い合わせの間に前後関係がなく、現在の状態に対応しています!

Output
入力データのセットごとに1行の出力に対応します.消去できる場合は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

Author

lwg

Recommend

We have carefully selected several similar problems for you: 1180 1072 1026 1240 1195

这题思路清晰，宽搜解题。其实深搜也可以，有兴趣的同学自己尝试。

贴代码，已做好详细注释：

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 1005;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int a[maxn][maxn],b[maxn][maxn],n,m;
int x1,x2,y2,y1,flag;
struct node{
    int x,y,dir,num;
}p,q;


bool check(){
   if (q.num>3) return 0;
   if (q.x<1 || q.y<1 || q.x>n || q.y>m ) return 0;
   if (a[q.x][q.y]!=0 &&(q.x!=x2 || q.y!=y2)) return 0;
   return 1;
}

void bfs(){
   p.x=x1;
   p.y=y1;
   p.dir=-1; //     -1，              3
   p.num=0;

   queueQ;
   Q.push(p); //  
   while(!Q.empty()){
       p=Q.front(); //     
       if (p.x==x2 && p.y==y2) {
          flag=1;
          return;
       }
       Q.pop(); //  
       for (int i=0;i<4;i++){
          q=p;
          q.x+=dx[i];
          q.y+=dy[i];
          if (q.dir!=i) {
                q.num++;
                q.dir=i; //    
          }
          if (check()) {
             a[q.x][q.y]=1; //    
             Q.push(q); //      
          }
       }
   }
}

int main(){
    while(cin>>n>>m && n && m){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);
        }
        memcpy(b,a,sizeof(a)); //       ，       
        int time;
        cin>>time;
        while(time--){
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            flag=0;
            if(x1==y1 && x2==y2) { //       
                printf("NO
");
                continue;
            }
            if (a[x1][y1]!=a[x2][y2] || a[x1][y1]==0 || a[x2][y2]==0) {
                printf("NO
");
                continue;
            }
            bfs();
            memcpy(a,b,sizeof(a));
            if (flag) printf("YES
");
            else printf("NO
");
        }
    }
    return 0;
}

商人が川を渡るMatlabプログラムの実現

NOI 2006最大利益(最大権閉鎖図)