Openjudge 仙岛求药 BFS queue

小咪咪 2022-06-17 11:47 176阅读 0赞

题目链接：http://noi.openjudge.cn/ch0205/2727/

是一个简单的BFS，这里重新熟悉了一下queue的使用

头文件\#include<queue>

成员函数：

<table style="color:rgb(0,0,0); font-family:Arial; font-size:14px; width:478px; height:130px"> 
 <tbody> 
  <tr> 
   <td>back</td> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> returns a reference to last element of a queue</p> </td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> true if the queue has no elements</p> </td> 
  </tr> 
  <tr> 
   <td>front</td> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> returns a reference to the first element of a queue</p> </td> 
  </tr> 
  <tr> 
   <td>pop</td> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> removes the top element of a queue</p> </td> 
  </tr> 
  <tr> 
   <td>push</td> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> adds an element to the end of the queue</p> </td> 
  </tr> 
  <tr> 
   <td>size</td> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> returns the number of items in the queue</p> </td> 
  </tr> 
 </tbody> 
</table>

一般而言 定义的时候这样 queue<int> q;

取出首个元素的操作 q.front() 弹出首个元素无返回值的操作 q.pop()

注意queue的清空没有clear这样的操作，但是可以用while不停的pop掉

写这么简单的题的时候遇到了一个比较蛋疼的bug,首先是上下左右，即dx, dy数组写的时候脑袋抽了

然后是多个案例的处理，我在完成第一个后，没有清空变量，即第二个案例没有很好的初始化

代码如下

// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    #include<stdio.h>
    #include<queue>
    #include<memory.h>
    using namespace std;
    
    struct pos
    {
    	int x, y, len;
    };
    
    queue<pos> q;
    
    int nx, ny, start_x, start_y, des_x, des_y;
    char ch;
    int con[25][25];
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    bool visit[25][25];
    
    int bfs(int x, int y)
    {
    	pos t1, t2;
    	t1.x = x; t1.y = y; t1.len = 0;
    	visit[x][y] = false;
    	//cout << x << " " << y << endl;
    	q.push(t1);
    	while (!q.empty())
    	{
    		t1 = q.front();
    		q.pop();
    		for (int i = 0; i < 4; i++) {
    			t2.x = t1.x + dx[i]; t2.y = t1.y + dy[i];
    			t2.len = t1.len + 1;
    			if (t2.x == des_x && t2.y == des_y) return t2.len;
    			if (t2.x < 0 || t2.x >= nx || t2.y < 0 || t2.y >= ny) continue;
    			if (visit[t2.x][t2.y] == false) continue;
    			if (con[t2.x][t2.y] == 2) continue;
    			visit[t2.x][t2.y] = false;
    			q.push(t2);
    			//cout << t2.x << " "<<t2.y << endl;
    		}
    	}
    	return -1;
    	
    }
    int main()
    {
    	while (1) 
    	{
    		memset(visit, true, sizeof(visit));
    		memset(con, 0, sizeof(con));
    		while (!q.empty()) q.pop();
    		cin >> nx >> ny;
    		if (nx == 0 && ny == 0) break;
    		for (int i=0; i<nx; i++)
    			for (int j = 0; j < ny; j++)
    			{
    				cin >> ch;
    				if (ch == '.') con[i][j] = 1;
    				if (ch == '#') con[i][j] = 2;
    				
    				if (ch == '@')
    				{
    					con[i][j] = 3;
    					start_x = i; start_y = j;
    				}
    				
    				if (ch == '*') {
    					con[i][j] = 4;
    					des_x = i; des_y = j;
    				}
    			}
    		
    		cout<<bfs(start_x, start_y)<<endl;
    		/*
    		for (int i = 0; i < nx; i++) {
    			for (int j = 0; j < ny; j++)
    				if (visit[i][j] == false) cout << " 1";
    				else cout << " 0";
    				cout << endl;
    		}
    		*/
    	}
        return 0;
    }