首页 > 搜索 > BFS搜索 > HDU 3130-Sir Bedavere’s Bogus Division Solutions-BFS-[解题报告]HOJ
2014
03-03

HDU 3130-Sir Bedavere’s Bogus Division Solutions-BFS-[解题报告]HOJ

Sir Bedavere’s Bogus Division Solutions

问题描述 :


The Brave Sir Robin’s cAsE  cOrReCtOr

The wise Sir Bedavere often uses non-standard logic, yet achieves positive results1.Well, it seems he has been at it again, this time with division. He has determined that canceling the common digit of a numerator and denominator produces the correct answer. Of course, Sir Bedavere only tried this on a small sample of three digit numbers. An example of what he did is shown in the following division problem (in which he canceled the common 6):

The Brave Sir Robin’s cAsE  cOrReCtOr

Your task is to find all three digit number combinations with the following property:

number combinations where removing the rightmost digit from the top number (numerator) and the identical leftmost digit from the bottom number (denominator) leaves the result of the calculation unchanged.

Omit all of the trivial cases ― xxx/xxx = xx/xx (222/222 = 22/22). The solutions are to be shown in increasing order of the top number (the numerator).

Hint

1 Please see the scene "How do you know she’s a witch?" or recall the quote "…how sheep’s bladders may be employed to prevent earthquakes."

输入:

NONE! There is no input for this problem.

输出:

NONE! There is no input for this problem.

样例输出:

217 / 775 = 21 / 75
249 / 996 = 24 / 96

HOJ 3130 Qie-Gao

//题意:此处略去好多字
//思路:BFS 记录搜索的起点和终点,
//      然后把他们所围的矩形的大小求出,然后再与搜索的步数比较,如果相等,说明这是切糕,不等不是
//hint:......
//     做啦一天搜索题目,这个题最有快感啦,一次a,貌似没有什么收获,
//     大一的秋季校赛题,表示也不过如此啊,为什么我当年校赛只a啦一题,擦,睡觉,哈哈
#include<iostream>
#include<queue>
#include<cstring>
#define maxlen 1010
using namespace std;
int mat[maxlen][maxlen];
int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
inline int abs(int a)
{
	return a > 0 ? a : -a;
}
struct node
{
    int x;
    int y;
};
int BFS(node s,int m,int n)
{
    node ne,ol,dr;
    int ans=0;
    queue<node> q;
    while(!q.empty())
    {
        q.pop();
    }
    q.push(s);
    mat[s.x][s.y]=0;
    while(!q.empty())
    {
        ol=q.front();
        q.pop();
        dr.x=ol.x;
        dr.y=ol.y;
        ans++;
        for(int i=0; i<4; i++)
        {
            ne.x=ol.x+dir[i][0];
            ne.y=ol.y+dir[i][1];
            if(ne.x<0||ne.y<0||ne.x>m-1||ne.y>n-1||mat[ne.x][ne.y]==0)continue;
            else
            {
                mat[ne.x][ne.y]=0;
                q.push(ne);
            }
        }
    }
    if(ans!=(abs(s.x-dr.x)+1)*(abs(s.y-dr.y)+1)) return -1;
    else return ans;
}
int main()
{
    bool flag;
    int m,n,i,j,sum,count;
    char k;
    node s;
    while(cin >> m >> n&&m&&n)
    {
        memset(mat,0,sizeof(mat));
        flag=true,sum=0;
        for(i=0; i<m; i++)
            for(j=0; j<n; j++)
            {
                cin >> k;
                if(k=='#') mat[i][j]=1;
            }
        for(i=0; i<m; i++)
            for(j=0; j<n; j++)
                if(mat[i][j]==1)
                {
                    s.x=i;
                    s.y=j;
                    count=BFS(s,m,n);
                    if(count>0) sum++;
                    else flag=false;
                }
        if(flag)  cout << sum << endl;
        else cout <<"Oh!My God!" << endl;
    }
    return 0;
}

参考:http://blog.csdn.net/hit1110310422/article/details/8545690


,
  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept