myhalfsea's Blog

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

struct node {
    int x,y;
    int time;
    bool operator< (const node t) const {
        return time>t.time;
    }
};

struct cmap {
    int nx,ny;
    char c;
}map[101][101];

int n,m;
int fight[101][101], mark[101][101];
priority_queue<node> que;

int bfs() {
    int k;
    int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
    node now,next;
    while(!que.empty())
        que.pop();
    now.x=n-1;now.y=m-1;
    if(map[now.x][now.y].c>='1' && map[now.x][now.y].c<='9') {
        now.time=map[n-1][m-1].c-'0';
        fight[now.x][now.y]=map[now.x][now.y].c-'0';
    }
    else
        now.time=0;
    que.push(now);
    while(!que.empty()) {
        now=que.top();
        que.pop();
        if(now.x==0 && now.y==0)
            return now.time;
        for(k=0;k<4;k++) {
            next.x=now.x+dir[k][0];
            next.y=now.y+dir[k][1];
            if(next.x>=0 && next.x<n && next.y>=0 && next.y<m && !mark[next.x][next.y] && map[next.x][next.y].c!='X') {
                if(map[next.x][next.y].c>='1' && map[next.x][next.y].c<='9') {
                    fight[next.x][next.y]=map[next.x][next.y].c-'0';
                    next.time=now.time+map[next.x][next.y].c-'0'+1;
                }
                else
                    next.time=now.time+1;
                que.push(next);
                map[next.x][next.y].nx=now.x;
                map[next.x][next.y].ny=now.y;
                mark[next.x][next.y]=1;
            }
        }
    }
    return -1;
}


int main()
{
    int i,j,flag,x,y,tx,ty,sec;
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF) {
        for(i=0;i<n;i++) {
            for(j=0;j<m;j++) {
                scanf(" %c",&map[i][j].c);
                mark[i][j]=fight[i][j]=0;
            }
        }
        mark[n-1][m-1]=1;
        flag=bfs();
        if(flag!=-1){
            printf("It takes %d seconds to reach the target position, let me show you the way.\n",flag);
            sec=1;x=y=0;
            while(sec!=flag+1) {
                printf("%ds:(%d,%d)->(%d,%d)\n",sec++,x,y,map[x][y].nx,map[x][y].ny);
                for(i=1;i<=fight[map[x][y].nx][map[x][y].ny];i++)
                    printf("%ds:FIGHT AT (%d,%d)\n",sec++,map[x][y].nx,map[x][y].ny);
                tx=map[x][y].nx;ty=map[x][y].ny;
                x=tx;y=ty;
            }
        }
        else
            printf("God please help our poor hero.\n");
        printf("FINISH\n");
    }
    return 0;
}

#include<iostream>
using namespace std;

//素数表,加快后续判断
int prime[38] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1}; 
int n, cas = 1;
int vis[21], num[21];

void dfs( int cur ) {
    int i;
    if ( cur == n && prime[num[0] + num[n-1]] ){ //递归边界,测试第一个数和最后一个数
        cout << num[0] ;
        for ( i = 1; i < n; i++ )
            cout << " "<< num[i];
         cout << endl;
    }
    else {
         for(int i = 2;i <= n; ++i) //尝试放置每一个数i
         if( !vis[i] && prime[i + num[cur-1]]) //如果i没有用过，并且与前面一个数之和为素数
         { 
             num[cur] = i;  //将该数放进A中
             vis[i] = 1;    //设置使用标志
             dfs(cur + 1);  //递归调用
             vis[i] = 0;    //将标志改回来,清除标志
         }
     }
}

int main()
{
    num[0] = 1;  //1的位置不变
    while ( cin >> n ) {
        memset(vis, 0, sizeof(vis) );  //标记数组清零
        cout << "Case " << cas++ <<":\n";
        dfs(1); 
        cout << endl; 
    }

    return 0;
}

STL之顺 序容器用法总结

顺序容器主要包括vector、list、deque，分别在头文件<vector>、<list> 和<deque>中定义。

1.容器创建

C<T>  c;               //创建空容器，适用于所有容器

C<T>  c(c2);         //创建c2的副本，c和c2必须是同类型容器和元素，适用所有容器

C<T>  c(b, e);       //容器类型和元素类型可兼容即可，

但是根据实验，貌似不行

C<T>  c(n, t);        //n个t值元素，t必须是T类型或可转为T类型，适用于顺序容器

C<T>  c(n);           //n个使用初始化值的元素，适用于顺序容器，一般是0

2.迭代器操作

*iter

iter->mem

++iter

iter++

--iter

iter--

iter1 == iter2

iter1 != iter2

--------------------------

iter + n                   //只有vector和deque支持算术运算和关系运算，list不支持

iter – n 

iter1 += iter2 

iter1 -= iter2 

iter1 – iter2 

iter1 > iter2 

iter1 < iter2 

iter1 <= iter2 

iter1 >= iter2

3.内 置类型

C<T>::size_type 

C<T>::iterator 

C<T>::const_iterator                //注意与const C<T>::iterator不同 

C<T>::reverse_iterator 

C<T>::const_reverse_iterator 

C<T>::value_type 

C<T>::reference                     //左值类型，即value_type& 

C<T>::const_reference           //const value_type&

4.基本操作

void  c.push_back(t); 

void  c.push_front(t);        //只适用list、deque

void  c.insert(p, n ,t); 

void  c.insert(p, b, e); 

C<T>::iterator  c.insert(p, t); 

C<T>::size_type  c.size(); 

C<T>::size_type  c.max_size();   //最多可容纳的元素，与类型有关，总存储空间固定 

bool  c.empyt(); 

void  c.resize(n); 

void  c.resize(n, t);                   //重调c的大小，新添加的元素值使用t值 

c[n]                                        //只适用于vector、deque容器 

C<T>::value_type  c.at(n);      //只适用于vector、deque容器，

防止越界

C<T>::iterator  c.erase(p); 

C<T>::iterator  e.erase(b, e); 

void  c.clear(); 

void  c.pop_back(); 

void  c.pop_front();               //只适用于list、deque容器 

c1 = c2                          //重设，要求c1和c2类型相同，元素类型相同 

void  c1.assign(b, e);      //重设，b、e不能是c1中的迭代器，类型兼容即可 

void  c1.assign(n, t);       //重设 

void  c1.swap(c2);        //c1和c2类型必须相同，且迭代器不失效

容 器适配器包括queue、priority_queue、stack。 

stack默认基于deque容器实现，也可以建立在vector、 list和deque上； 

queue默认基于deque容器实现，也可以建立在list和deque上； 

priority_queue默 认基于vector上，也可以建立在vector和deque上。 

stack<string, vector<string> >  a; 

stack<string, vector<string> >  a(c);

1. 内置类型

C<T>::size_type 

C<T>::value_type 

C<T>::container_type

2.stack 的操作

bool  s.empty(); 

C<T>::size_type  s.size(); 

void s.pop();                   //删除不返回 

C<T>::value_type  s.top();      //返回但不删除 

void s.push(value);

3.queue和 priority_queue的操作

void  q.empty(); 

C<T>::size_type  q.size(); 

void  q.pop();                         //删除队首，不返回 

C<T>::value_type  q.front();   //返回队首，不删除，只适用于queue 

C<T>::value_type  q.back();   //返回队尾，不删除，只适用于queue 

C<T>::value_type  q.top();    //返回最高优先级的元素，不删除，只适用于priority_type 

void  q.push(value);               //对queue是在队尾压入，对priority_queue是适当位置插入