首页 > 代码库 > HDU 4121 Xiangqi --模拟

HDU 4121 Xiangqi --模拟

题意: 给一个象棋局势,问黑棋是否死棋了,黑棋只有一个将,红棋可能有2~7个棋,分别可能是车,马,炮以及帅。

解法: 开始写法是对每个棋子,都处理处他能吃的地方,赋为-1,然后判断将能不能走到非-1的点。但是WA了好久,也找不出反例,但就是觉得不行,因为可能有将吃子的情况,可能有hack点。但是比赛后还是被我调出来了。

代码:

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>using namespace std;#define N 1017int chess[14][13],mp[14][13];  //0 : Non  1:G帅 2:R车 3:H Horse 4:C Cannonint dx[4] = {0,-1,0,1};int dy[4] = {1,0,-1,0};bool InPalace(int nx,int ny) { if(nx >= 1 && nx <= 3 && ny >= 4 && ny <= 6) return true; return false; }bool InChess(int nx,int ny)  { if(nx >= 1 && nx <= 10 && ny >= 1 && ny <= 9) return true; return false;}int main(){    int n,X,Y,i,j,k;    int x,y;    char ss[4];    while(scanf("%d%d%d",&n,&X,&Y)!=EOF && (n+X+Y))    {        memset(chess,0,sizeof(chess));        memset(mp,0,sizeof(mp));        for(i=1;i<=n;i++)        {            //0 : Non  1:G帅 2:R车 3:H Horse 4:C Cannon            scanf("%s%d%d",ss,&x,&y);            if(ss[0] == G)      chess[x][y] = 1;            else if(ss[0] == R) chess[x][y] = 2;            else if(ss[0] == H) chess[x][y] = 3;            else if(ss[0] == C) chess[x][y] = 4;        }        for(i=1;i<=10;i++)        {            for(j=1;j<=9;j++)            {                if(chess[i][j] == 1) // shuai                {                    for(k=i-1;k>=1;k--)                    {                        if(chess[k][j] != 0)                        {                            mp[k][j] = -1;                            break;                        }                        if(k <= 3 && chess[k][j] == 0) mp[k][j] = -1;                    }                }                else if(chess[i][j] == 2)  // R che                {                    for(int D=0;D<4;D++)                    {                        int kx = i, ky = j;                        while(1)                        {                            kx = kx + dx[D];                            ky = ky + dy[D];                            if(!InChess(kx,ky)) break;                            if(chess[kx][ky] == 0) mp[kx][ky] = -1;                            else                            {                                mp[kx][ky] = -1;                                break;                            }                        }                    }                }                else if(chess[i][j] == 3)   //Horse                {                    if(InChess(i-1,j) && chess[i-1][j] == 0 && (i-1 != X || j != Y))  //UP not blocked                    {                        if(InChess(i-2,j-1)) mp[i-2][j-1] = -1;                        if(InChess(i-2,j+1)) mp[i-2][j+1] = -1;                    }                    if(InChess(i+1,j) && chess[i+1][j] == 0 && (i+1 != X || j != Y))  //DOWN not blocked                    {                        if(InChess(i+2,j-1)) mp[i+2][j-1] = -1;                        if(InChess(i+2,j+1)) mp[i+2][j+1] = -1;                    }                    if(InChess(i,j+1) && chess[i][j+1] == 0 && (i != X || j+1 != Y))  //RIGHT not blocked                    {                        if(InChess(i-1,j+2)) mp[i-1][j+2] = -1;                        if(InChess(i+1,j+2)) mp[i+1][j+2] = -1;                    }                    if(InChess(i,j-1) && chess[i][j-1] == 0 && (i != X || j-1 != Y))  //LEFT not blocked                    {                        if(InChess(i-1,j-2)) mp[i-1][j-2] = -1;                        if(InChess(i+1,j-2)) mp[i+1][j-2] = -1;                    }                }                else if(chess[i][j] == 4)   //Cannon pao                {                    for(int D=0;D<4;D++)                    {                        int kx = i, ky = j;                        int cnt = 0;                        while(1)                        {                            kx = kx + dx[D];                            ky = ky + dy[D];                            if(!InChess(kx,ky)) break;                            if(cnt == 1 && chess[kx][ky] == 0) mp[kx][ky] = -1;                            if(chess[kx][ky] != 0)                            {                                if(cnt == 0) cnt++;                                else if(cnt == 1)                                {                                    mp[kx][ky] = -1;                                    break;                                }                            }                        }                    }                }            }        }        int tag = 0;        for(k=0;k<4;k++)        {            int kx = X + dx[k];            int ky = Y + dy[k];            if(!InChess(kx,ky) || !InPalace(kx,ky)) continue;            if(mp[kx][ky] != -1) { tag = 1; break; }  //可以走        }        if(tag) puts("NO");        else    puts("YES");    }    return 0;}
View Code

 

比赛中后来换了一种写法,枚举将能走的四个位置,然后判断此时是否能被吃掉。 如果没有一个安全的地方,那么就死棋了。 这种写起来就好些多了。

代码:

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>using namespace std;#define N 1017int chess[14][13],mp[14][13];  //0 : Non  1:G帅 2:R车 3:H Horse 4:C Cannonint dx[4] = {0,-1,0,1};int dy[4] = {1,0,-1,0};bool InPalace(int nx,int ny){    if(nx >= 1 && nx <= 3 && ny >= 4 && ny <= 6) return true;    return false;}bool InChess(int nx,int ny){    if(nx >= 1 && nx <= 10 && ny >= 1 && ny <= 9) return true;    return false;}struct node{    int x,y,type;}q[10];bool Check(int X,int Y,int i,int j,int type)  //将死则 return false !{    int k;    if(type == 1)     //    {        if(j != Y) return true;   //不是一行        for(k=i-1;k>X;k--)        {            if(chess[k][j] != 0)                break;        }        if(k == X) return false;  //老倌子见面,gg        return true;    }    else if(type == 2)       //R    {        int tag = 1;        for(int D=0;D<4;D++)        {            int kx = i, ky = j;            while(1)            {                kx = kx + dx[D];                ky = ky + dy[D];                if(!InChess(kx,ky)) break;                if(kx == X && ky == Y)  //车能碰到将                {                    tag = 0;                    break;                }                if(chess[kx][ky] != 0)                    break;            }        }        if(!tag) return false;        return true;    }    else if(type == 3)  //Horse    {        int tag = 1;        if(InChess(i-1,j) && chess[i-1][j] == 0 && (i-1 != X && j != Y))  //UP not blocked        {            if(InChess(i-2,j-1) && i-2 == X && j-1 == Y)                tag = 0;             if(InChess(i-2,j+1) && i-2 == X && j+1 == Y)                tag = 0;        }        if(InChess(i+1,j) && chess[i+1][j] == 0 && (i+1 != X && j != Y))  //DOWN not blocked        {            if(InChess(i+2,j-1) && i+2 == X && j-1 == Y)                tag = 0;            if(InChess(i+2,j+1) && i+2 == X && j+1 == Y)                tag = 0;        }        if(InChess(i,j+1) && chess[i][j+1] == 0 && (i != X && j+1 != Y))  //RIGHT not blocked        {            if(InChess(i-1,j+2) && i-1 == X && j+2 == Y)                tag = 0;            if(InChess(i+1,j+2) && i+1 == X && j+2 == Y)                tag = 0;        }        if(InChess(i,j-1) && chess[i][j-1] == 0 && (i != X && j-1 != Y))  //LEFT not blocked        {            if(InChess(i-1,j-2) && i-1 == X && j-2 == Y)                tag = 0;            if(InChess(i+1,j-2) && i+1 == X && j-2 == Y)                tag = 0;        }        if(!tag) return false;        return true;    }    else if(type == 4)         //Cannon    {        int tag = 1;        for(int D=0;D<4;D++)        {            int kx = i, ky = j;            int cnt = 0;            while(1)            {                kx = kx + dx[D];                ky = ky + dy[D];                if(!InChess(kx,ky)) break;                if(cnt == 1 && kx == X && ky == Y)                {                    tag = 0;                    break;                }                if(chess[kx][ky] != 0)                    cnt++;            }        }        if(!tag) return false;        return true;    }    return false;}int main(){    int n,X,Y,i,j,k;    int x,y;    char ss[4];    while(scanf("%d%d%d",&n,&X,&Y)!=EOF && (n+X+Y))    {        memset(chess,0,sizeof(chess));        int tot = 0;        for(i=1;i<=n;i++)        {            //0 : Non  1:G帅 2:R车 3:H Horse 4:C Cannon            scanf("%s %d%d",ss,&x,&y);            if(ss[0] == G)                chess[x][y] = 1;            else if(ss[0] == R)                chess[x][y] = 2;            else if(ss[0] == H)                chess[x][y] = 3;            else if(ss[0] == C)                chess[x][y] = 4;            node now;            now.x = x, now.y = y, now.type = chess[x][y];            q[++tot] = now;        }        int flag[10];        int tag = 0;        for(k=0;k<4;k++)        {            int nx = X + dx[k];            int ny = Y + dy[k];            memset(flag,0,sizeof(flag));            if(!InChess(nx,ny) || !InPalace(nx,ny)) continue;            for(i=1;i<=tot;i++)            {                if(nx == q[i].x && ny == q[i].y)                {                    flag[i] = 1;                    chess[nx][ny] = 0;                }            }            int smalltag = 1;            for(i=1;i<=tot;i++)            {                if(flag[i]) continue;                bool res = Check(nx,ny,q[i].x,q[i].y,q[i].type);                if(!res) { smalltag = 0; break; }            }            if(smalltag)            {                tag = 1;                break;            }            // 还原            for(i=1;i<=tot;i++)            {                if(flag[i])                    chess[q[i].x][q[i].y] = q[i].type;            }        }        if(tag) puts("NO");        else    puts("YES");    }    return 0;}
View Code

 

HDU 4121 Xiangqi --模拟