UVA 1600-- Patrol Robot （bfs）

这题。。 开始把题目看错了，k表示最大连续数，机器人最多连续通过k个障碍

然后开始写，wa掉了

一直wa 改不成功，这个的状态存储有点问题，对于连续障碍的更新有问题，并且有些障碍的位置不能只存储一次，存储一次会错的

想不出来这种方法怎么修正，用一个dd[][] 去存储状态 当遇到下一个点为0是dd应该复原，但是值得注意的是，在for循环内部，dd应该是不变的，只是对应状态改变

所以二维我不知道怎么改了，看来只好用三维的 带障碍数；

错误代码

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const int maxn=25;
int n,m;
int mp[maxn][maxn];
int vis[maxn][maxn];
int d[maxn][maxn];
int k;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int dd[maxn][maxn];
int dfs()
{
    memset(d,0xff,sizeof(d));
    memset(dd,0xff,sizeof(dd));
    queue<pair<int,int> > q;
    q.push(make_pair(0,0));
    d[0][0]=0;
    while(q.size())
    {
        pair<int,int> a=q.front();

        q.pop();
        if(a.first==n-1&&a.second==m-1)
        {
            return d[a.first][a.second];
        }
        for(int i=0;i<4;i++)
        {
            int xx=dx[i]+a.first,yy=dy[i]+a.second;
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&d[xx][yy]<0&&!mp[xx][yy])
            {
                d[xx][yy]=d[a.first][a.second]+1;
                q.push(make_pair(xx,yy));
                dd[a.first][a.second]=-1;
                //cout<<"push1"<<endl;

            }
             else if(xx>=0&&xx<n&&yy>=0&&yy<m&&mp[xx][yy]&&dd[a.first][a.second]+1<k)
            {
                //cout<<"? "<<a.first<<" "<<a.second<<"dd   a"<<dd[a.first][a.second]<<endl;
               // cout<<"? "<<a.first<<" "<<a.second<<endl;
              //  cout<<xx<<" "<<yy<<endl;999999809-
               if(d[xx][yy]<0)
                q.push(make_pair(xx,yy));
                if(d[xx][yy]<0||d[xx][yy]>d[a.first][a.second]+1)
                d[xx][yy]=d[a.first][a.second]+1;
                if(dd[xx][yy]<0||dd[xx][yy]>dd[a.first][a.second]+1)
                dd[xx][yy]=dd[a.first][a.second]+1;

                // cout<<"push2"<<endl;

            }
        }

    }
    return -1;

}
int main()
{
    //freopen("out.txt","w",stdout);
    int T;
    cin>>T;
    while(T--)
    {
         cin>>n>>m>>k;
         memset(vis,0,sizeof(vis));
         memset(mp,0,sizeof(mp));
         for(int i=0;i<n;i++)
             for(int j=0;j<m;j++)
                cin>>mp[i][j];
        int ans=dfs();
        cout<<ans<<endl;
    }
    return 0;
}

更新的等会写。。

我又gg了  ，身体是革命的本钱，身体不好的人，简直无能为力，头疼到没法敲代码，卧槽强撑撑住啊，下午还要打选拔赛呢，要是不能出线，那就等着gg吧！！！！

正确代码：网上的（懒人找借口，等会敲）

#include <stdio.h> 
#include <string.h>
#include <queue>
using namespace std;

int g[32][32];
int dist[32][32][32];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
    int testcase;
    int N, M, K;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                scanf("%d", &g[i][j]);
        memset(dist, 63, sizeof(dist));
        dist[0][0][0] = 0;
        queue<int> X, Y, S;
        int x, y, s, tx, ty, ts;
        X.push(0), Y.push(0), S.push(0);
        while (!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            s = S.front(), S.pop();
            for (int i = 0; i < 4; i++) {
                tx = x + dx[i], ty = y + dy[i];
                if (tx < 0 || ty < 0 || tx >= N || ty >= M)
                    continue;
                if (g[tx][ty])
                    ts = s + 1;
                else
                    ts = 0;
                if (ts > K)	continue;
                if (dist[tx][ty][ts] > dist[x][y][s] + 1) {
                    dist[tx][ty][ts] = dist[x][y][s] + 1;
                    X.push(tx), Y.push(ty), S.push(ts);
                }
            }
        }
        int ret = 0x3f3f3f3f;
        for (int i = 0; i <= K; i++)
            ret = min(ret, dist[N-1][M-1][i]);
        printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
    }
    return 0;
}