滑雪者路径耗时计算C#代码错误排查：重复路径段统计异常

问题描述 #

滑雪者在雪场滑行，移动由'S'（向南10米）、'N'（向北10米）、'W'（向西10米）、'E'（向东10米）的字符序列描述。规则：首次滑行未访问路径段耗时5秒，重复滑行已访问路径段耗时1秒，需计算完成整个路径的总耗时。

输入格式 #

• 第一行输入整数t（查询次数）
• 每行查询为一串仅包含'S'/'N'/'W'/'E'的字符串

用户提交的C#代码 #

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp8
{
    public class Position
    {
        public int X { get; set; }
        public int Y { get; set; }
    }

    public class Program
    {
        static void Main(string[] args)
        {
            var requestCount = Convert.ToInt16(Console.ReadLine());

            var results = new List<int>();

            for (int i = 0; i < requestCount; i++)
            {
                var movments = Console.ReadLine()
                                      .ToCharArray()
                                      .ToList();

                results.Add(GetMovmentPrice(movments));
            }

            Console.WriteLine(string.Join("\n", results));
        }

        static int GetMovmentPrice(List<char> movments)
        {
            var postion = new Position { X = 0, Y = 0 };
            var knownPositions = new Dictionary<Position, bool>();
            knownPositions.Add(new Position { X = postion.X, Y = postion.Y }, true);

            var price = 0;

            foreach (var movment in movments)
            {
                switch (movment)
                {
                    case 'N':
                        postion.Y++;
                        break;
                    case 'S':
                        postion.Y--;
                        break;
                    case 'W':
                        postion.X--;
                        break;
                    case 'E':
                        postion.X++;
                        break;
                }

                bool founded = false;

                foreach (var key in knownPositions.Keys)
                {
                    if (key.X == postion.X && key.Y == postion.Y)
                    {
                        price += 1;
                        founded = true;
                        break;
                    }
                }

                if (founded)
                    continue;

                price += 5;
                knownPositions.Add(new Position { X = postion.X, Y = postion.Y }, true);

            }
            return price;
        }
    }
}

问题重现 #

测试输入 #

5
S
SENNWWEENWESNEEWSWNSNNENSNWSNWSSNNNWSWNNNWNENESNNNSEEEWEWEEWNEWNWSSWENSWSSNNE
EWEENWWWNENENNSSEEWENNWSSWSNSENENWWEEENESNSSESSSEWEESNESSESSSNENSNWNWWWESWEEWEESSSES
SWNEWNESWWSWENENSSNWEWNWNNWNWWEWEWNNSWNEESNSNWSSENWSWSWSNESSSEWESSESWWENWWSWNSWWNEWSNNWE
WNWNSSNWESENEEWSEENENSWWWESSNNESENNENNNWNEWWSEWESSSNSWSENWEESSEESESNWSWSEEWESNSSNS

用户代码输出 #

5
249
280
276
246

正确输出 #

5
265
304
300
278

错误原因分析 #

1. 核心逻辑错误：代码错误地用「终点位置是否已被访问」来判断路径段是否重复，而题目要求判断的是「当前滑行的路径段（两个相邻位置之间的线段）是否已被滑行过」。即使终点位置已经到达过，只要这段路径是第一次走，就应该加5秒，而不是1秒。
2. 效率问题：使用Dictionary<Position, bool>存储位置，由于Position是自定义引用类型，默认的相等比较是引用相等而非值相等。虽然代码通过遍历所有键手动比较X/Y值实现了值相等判断，但这种方式效率极低。

修复方案 #

修复后的代码 #

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp8
{
    public class Program
    {
        static void Main(string[] args)
        {
            if (!int.TryParse(Console.ReadLine(), out int requestCount))
            {
                return;
            }

            var results = new List<int>();

            for (int i = 0; i < requestCount; i++)
            {
                var movements = Console.ReadLine()?.Trim() ?? string.Empty;
                results.Add(GetMovementCost(movements));
            }

            Console.WriteLine(string.Join("\n", results));
        }

        static int GetMovementCost(string movements)
        {
            int x = 0, y = 0;
            // 存储无向路径段，用ValueTuple存储排序后的两个位置，确保A→B和B→A是同一个键
            var visitedSegments = new HashSet<((int x, int y), (int x, int y))>();
            int totalCost = 0;

            foreach (var move in movements)
            {
                int newX = x, newY = y;
                switch (move)
                {
                    case 'N':
                        newY++;
                        break;
                    case 'S':
                        newY--;
                        break;
                    case 'W':
                        newX--;
                        break;
                    case 'E':
                        newX++;
                        break;
                }

                // 生成路径段的键：将两个位置按坐标从小到大排序，确保无向
                var point1 = (x, y);
                var point2 = (newX, newY);
                var segment = point1.CompareTo(point2) <= 0 ? (point1, point2) : (point2, point1);

                if (visitedSegments.Contains(segment))
                {
                    totalCost += 1;
                }
                else
                {
                    totalCost += 5;
                    visitedSegments.Add(segment);
                }

                // 更新当前位置
                x = newX;
                y = newY;
            }

            return totalCost;
        }
    }

    // 为ValueTuple<int, int>扩展比较方法，用于排序路径段的两个点
    public static class TupleExtensions
    {
        public static int CompareTo(this (int x, int y) a, (int x, int y) b)
        {
            if (a.x != b.x)
                return a.x.CompareTo(b.x);
            return a.y.CompareTo(b.y);
        }
    }
}

修复说明 #

1. 路径段存储：使用HashSet<((int x, int y), (int x, int y))>存储已经走过的无向路径段。对于每一步的起点和终点，将两个点按坐标从小到大排序后生成路径段键，确保A→B和B→A被视为同一个键。
2. 逻辑修正：每次滑行前，先判断当前路径段是否已存在于集合中：
   • 存在：重复滑行，加1秒
   • 不存在：首次滑行，加5秒并将路径段加入集合
3. 效率优化：使用ValueTuple作为键，避免了自定义引用类型的相等比较问题，同时HashSet的查找是O(1)时间复杂度，比原代码的遍历查找效率高得多。
4. 输入健壮性：增加了int.TryParse和空输入处理，避免程序因非法输入崩溃。

测试验证 #

使用提供的测试输入运行修复后的代码，将得到与正确输出一致的结果。

内容的提问来源于stack exchange，提问作者Mar Tin