poj模拟题总结（一）

模拟是acm算法中基础但深奥的算法，不容轻视。

本次模拟题练习题为1835，2623，2271，2996，2706，1676，1472，1027，3371。

1835 宇航员：可以以左手，脸，头三个参量的方向来确定自己的方向。自己比划比划即可。

2996：棋盘问题，比较水。

2706：线段相交+DFS，注意线段相交的判断。

1676：DFS即可。

1472：典型的递归题，构建栈。同时可以建立一个class，来表示一个多项式，利用操作符重载来简化代码结构。

1027：模拟，代码不像网上说的那么繁琐，我认为还可以。但值得练练。

3371：字符串处理，细心题。

下面将贴出2706，1472，1027代码，这三题在本次练习中稍繁。

2706代码：

[cpp]
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int N=25,M=255;
const int dx[8]={1,2,2,1,-1,-2,-2,-1};
const int dy[8]={2,1,-1,-2,-2,-1,1,2};

struct point
{
    int x,y;
    point(int xx=0,int yy=0)
    {
        x=xx;y=yy;
    }
};

struct line
{
    point a,b;
    line(point aa=point(),point bb=point())
    {
        a=aa;b=bb;
    }
}l[N*N];

int tot,n,m;
bool v[2][N][N],vv[N][N][N][N],vis[N][N];

bool dfs(int x,int y)
{
    vis[x][y]=true;
    if (x==n) return true;
    for (int k=0;k<8;k++)
        if (x+dx[k]>=0 && x+dx[k]<=n && y+dy[k]>=0 && y+dy[k]<=n
        && !vis[x+dx[k]][y+dy[k]] &&vv[x][y][x+dx[k]][y+dy[k]])
        {
            if (dfs(x+dx[k],y+dy[k])) return true;
        }
    return false;
}

int xmult(point a,point b,point c)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

bool intersect(point p1,point q1,point p2,point q2)
{
    return xmult(p2,q1,p1)*xmult(q2,q1,p1)<0 && xmult(p1,q2,p2)*xmult(q1,q2,p2)<0;
}

int main()
{
    int i,j,k,x,y,col;
    freopen("in.txt","r",stdin);
    while (1)
    {
        ppp:
        cin >> n >> m;
        if (n==0 && m==0) break;
        memset(v,0,sizeof(v));
        memset(vv,0,sizeof(vv));
        tot=0;
        for (i=1;i<=m;i++)
        {
            cin >> x >> y;
            col=i%2;
            v[col][x][y]=true;
            for (k=0;k<8;k++)
                if (x+dx[k]>=0 && x+dx[k]<=n && y+dy[k]>=0 && y+dy[k]<=n && v[col][x+dx[k]][y+dy[k]])
                {
                    point p2=point(x+dx[k],y+dy[k]);
                    point p1=point(x,y);
                    bool ff=true;
                    for (j=1;j<=tot;j++)
                        if (intersect(l[j].a,l[j].b,p1,p2))
                        {
                            ff=false;
                            break;
                        }
                    if (ff)
                    {
                        l[++tot]=line(p1,p2);
                        if (col==1)
                        {
                            vv[p1.x][p1.y][p2.x][p2.y]=true;
                            vv[p2.x][p2.y][p1.x][p1.y]=true;
                        }
                    }
                }
        }
        for (i=0;i<n;i++)
        {
            memset(vis,0,sizeof(vis));
            if (v[1][0][i] && dfs(0,i))
            {

补充：软件开发 , C++ ,