Submission #1040788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040788		GuessWhoHas2Cats	Tracks in the Snow (BOI13_tracks)	C++14	75.31 / 100	377 ms	125956 KiB

tracks

#include<bits/stdc++.h>
#define a first
#define b second
using namespace std;
typedef pair<int, int>PII;
const int MAXL = 4000;
int n, m;
vector<string>graph;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main()
{
    int ans = 1; // 至少有一个animal
    iostream :: sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    graph.resize(n);
    for(int i = 0; i < n; i ++)
        cin >> graph[i];
    // 0-1 bfs 0 -> push_front, 1 -> push_back() --> increasing deque
    // q 存储位置
    // dist 存储到 start 的距离
    deque<PII>q;
    q.push_back({0, 0});
    vector<vector<int>>dist(n, vector<int>(n, INT_MAX));
    dist[0][0] = 1; // 根的depth是1
    while(q.size())
    {
        auto t = q.front();
        q.pop_front();
        ans = max(ans, dist[t.a][t.b]);//已可用它更新其它点的dist是否最大

        // 字母走方向的图不是adj的图
        for(int i = 0; i < 4; i ++)
        {
            int x = t.a + dx[i], y = t.b + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= m)continue;
            if(graph[x][y] == '.' || dist[x][y] != INT_MAX)continue;// un-visited
            // 在同一node内，weight为0
            if(graph[x][y] == graph[t.a][t.b])
            {
                q.push_front({x, y});
                dist[x][y] = dist[t.a][t.b];
            }
            else
            {
                q.push_back({x, y});
                dist[x][y] = dist[t.a][t.b] + 1;
            }

        }
    }
    cout << ans << endl;
    return 0;
}

• Subtask 1: 25 / 30
• Subtask 2: 50.3125 / 70