NOJ 1009连连看

[1009] 连连看
时间限制: 1000 ms　内存限制: 65535 K
问题描述
大家都知道一个曾经风靡一时的游戏：连连看。 XadillaX在做连连看的时候不专心，做做就去玩别的去了，但他想早点完成这个小游戏，于是他找到你来帮他完成连连看的一段核心代码。首先会给出一副连连看的分布图形，然后会给你各种鼠标点击操作（鼠标点击的坐标），你的工作就是算出最后还剩下几个方块。鼠标操作之后的判断是这样的：在没有记录任何图形的情况下，第一下点击会记录当前点击的图形，第二下以及之后的每次点击都会记录点击的图形，并且与之前的图形对比，如果可消就消掉两块，如果不可消就将之前之前点击的图形取消记录（但不取消记录当前点击的图形）。可消的概念就是能在两次拐角内能连接起来，并且两个图形是相同的。若点击的是空块，则不做任何操作。
输入
第一行一个正整数T（0 < T <= 10），表示数据组数。
接下来T组数据，每组数据的第一行是两个正整数n和m(2 <= m, n <= 100)，表示连连看分布图的高和宽（每个图形占一个单位高和宽）。
接下来n行表示图形的分布，由大写'A'~'Z'以及'0'组成，其中大写字母代表一个图形（相同字母的表示图形相同），'0'表示这个地方为空。
接下来一行为一个正整数Q(1 <= Q <= 100)，代表鼠标操作次数。
最后Q行，每行有两个正整数，代表鼠标点击的坐标Xi, Yi(0 <= Xi, Yi, < 100)。
输出
对于每组，输出个正整数，代表本组数据最终会剩下几个图形。一组数据占一行。
样例输入

样例输出
4
思路：哈哈哈哈，模拟呀~~
用BFS搜就行啦，记录转弯次数，超过2次的直接GG掉
然后搜之前在外围补一圈0，别问为什么。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k,lx,ly,nx,ny,flag;
int f[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
char mp[105][105];
bool vis[105][105];
bool jug(int x,int y,int tx,int ty)
{
    if(x<0||x>n+1||y<0||y>m+1)return false;
    if(mp[x][y]=='0')
    return true;
    if(x==tx&&y==ty)
    return true;
    return false;
}
struct node
{
    int x,y,turn,f;
};
int bfs(int sx,int sy,int tx,int ty)
{
    node s,t;
    queue<node> q;
    s.x=sx,s.y=sy,s.turn=0,s.f=-1;
    q.push(s);
    while(!q.empty())
    {
        s=q.front();q.pop();//printf("%d %d %d
",s.x,s.y,s.turn);
        if(s.x==tx&&s.y==ty&&s.turn<=3)
        {   //printf("asdasd
");
            mp[sx][sy]='0';mp[tx][ty]='0';return 1;
        }
        for(int i=0;i<4;i++)
        {
            t.x=s.x+f[i][0],t.y=s.y+f[i][1];
            if(jug(t.x,t.y,tx,ty)&&!vis[t.x][t.y])
            {
                vis[t.x][t.y]=1;
                if(s.f!=i)t.turn=s.turn+1;
                else t.turn=s.turn;
                t.f=i;
                if(t.turn<=3)
                q.push(t);
            }
        }
    }
    return 0;
}
int main()
{
    int T,ans;
    scanf("%d",&T);
    while(T--)
    {   flag=0;ans=0;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%s",mp[i]+1);
        for(int i=0;i<=n+1;i++)
        {
            for(int j=0;j<=m+1;j++)
            {
                if(i==0||i==n+1)mp[i][j]='0';
                if(j==0||j==m+1)mp[i][j]='0';
            }
        }
        scanf("%d",&k);
        lx=-1,ly=-1;
        for(int i=1;i<=k;i++)
        {
           scanf("%d %d",&ny,&nx);
           ny++,nx++;
           if(lx!=-1&&ly!=-1)
           {
               if(mp[nx][ny]==mp[lx][ly]&&mp[nx][ny]!='0')
               memset(vis,0,sizeof(vis)),flag=bfs(nx,ny,lx,ly);
           }//printf("%d %d %d %d %d
",flag,lx,ly,nx,ny);
           if(mp[nx][ny]!='0'&&!flag)
           lx=nx,ly=ny;
           if(flag)
           lx=-1,ly=-1,flag=0;
        }
     //   for(int i=1;i<=n;i++)
      //      printf("%s
",mp[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            if(mp[i][j]!='0')ans++;
        printf("%d
",ans);
    }
    return 0;
}

NOJ 1009连连看

[1009] 连连看