学习心得(code)

superlong@CoreCoder

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

公告

文字可能放在http://blog.csdn.net/superlong100,此处存放代码

常用链接

留言簿(4)

我参与的团队

搜索

  •  

最新随笔

最新评论

  • 1. re: Poj 1279
  • 对于一个凹多边形用叉积计算面积 后能根据结果的正负来判断给的点集的时针方向?
  • --bsshanghai
  • 2. re: Poj 3691
  • 你写的这个get_fail() 好像并是真正的get_fail,也是说fail指向的串并不是当前结点的子串。为什么要这样弄呢?
  • --acmer1183
  • 3. re: HDU2295[未登录]
  • 这个是IDA* 也就是迭代加深@ylfdrib
  • --superlong
  • 4. re: HDU2295
  • 评论内容较长,点击标题查看
  • --ylfdrib
  • 5. re: HOJ 11482
  • 呵呵..把代码发在这里很不错..以后我也试试...百度的编辑器太烂了....
  • --csuft1

阅读排行榜

评论排行榜

#include <iostream>
#include 
<queue>
#include 
<string>
using namespace std;

int r, c;

char  map[1001][1001];
bool  hash[1001][1001];
int   tu[1001][1001];

void read()
{
    scanf(
"%d %d"&r, &c);
    getchar();
    
for(int i = 0; i < r; i ++) gets(map[i]);
}

struct nod
{
    
int x, y;
};

int move[4][2]={{-10}, {01}, {10}, {0-1}};

queue 
<nod> q;

bool check(nod st)
{
    
if(st.x < 0 || st.y < 0 || st.x >=|| st.y >= c)
        
return false;
    
if(map[st.x][st.y] == '#' || map[st.x][st.y] == 'J'return false;
    
return true;
}

void bfs()
{
    
int i, j, step = 0, size;
    nod temp, t;
    
while(!q.empty())
    {
        size 
= q.size();
        
while(size --)
        {
            temp 
= q.front();
            q.pop();
            
for(i = 0; i < 4; i ++)
            {
                t.x 
= temp.x + move[i][0];
                t.y 
= temp.y + move[i][1];     
                
if(tu[t.x][t.y] > step + 1 && check(t))
                {
                    tu[t.x][t.y] 
= step + 1;
                    q.push(t);
                }
            }   
        }
        step 
++;
    }
}

bool final(nod sta)
{
    
if(sta.x < 0 || sta.y < 0 || sta.x >= r || sta.y >= c)
        
return true;
    
return false;
}

bool ok(nod sta, int step)
{
    
if(map[sta.x][sta.y] == '#' || tu[sta.x][sta.y] <= step + 1 || hash[sta.x][sta.y])
        
return false;
    
return true;
}

bool expend(nod sta, int step)
{
    nod t;
    
for(int i = 0; i < 4; i ++)
    {
        t.x 
= sta.x + move[i][0];
        t.y 
= sta.y + move[i][1];
        
if(final(t))       return true;
        
if(ok(t, step))    
        {
            hash[t.x][t.y] 
= 1;
            q.push(t);
        }
    }
    
return false;
}

int bfs_person(int x, int y)
{
    
int i, j, step = 0, size;
    
while(!q.empty()) q.pop();
    nod temp, t;
    temp.x 
= x;
    temp.y 
= y;
    q.push(temp);
    
while(!q.empty())
    {
        size 
= q.size();
        
while(size --)
        {
            temp 
= q.front();
            q.pop();
            
if(expend(temp, step)) return step + 1;
        }
        step 
++;
    }
    
return -1;
}

void solve()
{
    
int i, j, x, y;
    nod tp;
    
for(i = 0; i < r; i ++)
    
for(j = 0; j < c; j ++)
        tu[i][j] 
= 999999;
    
while(!q.empty()) q.pop();
    
for(i = 0; i < r; i ++)
    
for(j = 0; j < c; j ++)
    {
        
if(map[i][j] == 'F')
        {
            tp.x 
= i;    tp.y = j;
            tu[i][j] 
= 0;
            q.push(tp);
        }
        
if(map[i][j] == 'J')
        {
            x 
= i;
            y 
= j;
        }
    }
    bfs();
    
    
int ans = bfs_person(x, y);
    
if(ans < 0) puts("IMPOSSIBLE");
    
else        printf("%d\n",ans);
    
}

int main()
{
    read();
    solve();
}

posted on 2009-08-28 20:26 superlong 阅读(92) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理