ertong

用户名：ruozhiertong

访问量：498

签　名：

ruozhiertong

等　　级
排　　名	3516
经　　验	1910
参赛次数	2
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

找寻小妖-题解(C语言代码)
浏览：175

你可能喜欢

A+B for Input-Output Practice (IV) （C语言代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

找寻小妖-题解(C语言代码)

　　作者: ertong　　　　发表时间：2019-06-17 15:45:43 浏览：175　|　评论：1　

原题链接：找寻小妖

这是吐槽贴。
为什么OJ不做的好一点？比如代码不AC，起码也要给出不AC的原因或者跑不通的样本数据等。而且对于数据输入scanf，也是不知所措。 比如以下代码，逻辑都差不多。 本地跑了都通过，但是一个通过，一个不通过。(不讨论设计的好坏). 最后再贴一个Java实现，还是无法AC。 第一个代码AC。其余两个和第一个一样的逻辑，就是无法AC，本地可以通过样本示例。
   
	#include <stdio.h>
    
    int M, N;
    char arr[105][105];
    int visit[105][105];
    
    
    typedef struct point
    {
        int x;
        int y;
        int step;
    }Point;
    
    int bfs(int beginX, int beginY)
    {
        Point startP;
        Point myQueue[105*105];
        int count = 0;
        int bottom = 0;
        int top = 0;
        startP.x = beginX;
        startP.y = beginY;
        startP.step = 0;
    
    
        //入队。
        myQueue[top++] = startP;
        count++;
        visit[beginX][beginY] = 1;
    
    
        while(count != 0)
        {
            //出队
            Point nowP = myQueue[bottom++];
            count--;
    
    
            if(arr[nowP.x][nowP.y] == '*')
                return nowP.step;
    
            //上下左右
            for(int i = 0; i < 4; i++)
            {
                Point nextP = nowP;
                switch(i)
                {
                    case 0:
                        nextP.x = nowP.x - 1;
                        break;
                    case 1:
                        nextP.x = nowP.x + 1;
                        break;
                    case 2:
                        nextP.y = nowP.y - 1;
                        break;
                    case 3:
                        nextP.y = nowP.y + 1;
                        break;
                }
    
                if(nextP.x < 0 || nextP.x >= M  || nextP.y < 0 || nextP.y >= N)
                    continue;
    
                if(visit[nextP.x][nextP.y] == 1)
                    continue;
    
                nextP.step = nowP.step + 1;
                //入队。
                myQueue[top++] = nextP;
                count++;
                visit[nextP.x][nextP.y] = 1;
            }
        }
        return -1;
    }
    
    int main()
    {
        scanf("%d%d",&M,&N);
        
    
        //这个输入居然不行。这个OJ 做的真烂。
        // getchar();//消除 \n
        // for(int i = 0; i < M ;i++)
        // {
        //     for (int j = 0; j < N; j++)
        //     {
        //         scanf("%c",&arr[i][j]);
        //         if(arr[i][j] == '#')
        //             visit[i][j] = 1;
        //         else
        //             visit[i][j] = 0;
        //     }
        //     getchar(); //消除 \n
            
        // }
    
        for(int i=0;i<M;i++)
            scanf("%s",arr[i]);
    
        //这个输入居然不行。这个OJ 做的真烂。
        // for(int i = 0; i < M ;i++)
        // {
        //     for (int j = 0; j < N; j++)
        //     {
        //         scanf("%c",&arr[i][j]);
        //     }
        //     getchar(); //消除 \n   
        // }
        
        int x = -1 ,y = -1;
        for(int i = 0; i < M; i++)
        {
            for(int j = 0; j < N; j++)
            {
                if(arr[i][j] == '@')
                {
                    x = i;
                    y = j;
                }
    
                if(arr[i][j] == '#')
                    visit[i][j] = 1;
                else
                    visit[i][j] = 0;
            }
        }
      
        int cost = bfs(x,y);
        if(cost == -1)
        	printf("Impossibility!\n");
        else
        	printf("%d\n", cost);
        
        return 0;
    }

**Java版本**

import java.io.IOException;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    class Point {
    	public int x;
    	public int y;
    	public int step;
    	
    	public Point(Point p) {
    		this.x  = p.x;
    		this.y = p.y;
    		this.step = p.step;
    	}
    
    	public Point() {
    		// TODO Auto-generated constructor stub
    	}
    }
    
    public class FindMonster {
    
    	static int M, N;
    	static char arr[][] = new char[105][105];
    	static int[][] visit = new int[105][105];
    	private static Scanner sc;
    
    	public static int bfs(int beginX, int beginY) {
    		Point startP = new Point();
    		Queue<Point> myQueue = new LinkedList<Point>();
    
    		startP.x = beginX;
    		startP.y = beginY;
    		startP.step = 0;
    		// 入队。
    		myQueue.offer(startP);
    		visit[beginX][beginY] = 1;
    
    		while (!myQueue.isEmpty()) {
    			// 出队
    			Point nowP = myQueue.poll();
    			
    			if (arr[nowP.x][nowP.y] == '*')
    				return nowP.step;
    
    			// 上下左右
    			for (int i = 0; i < 4; i++) {
    				Point nextP = new Point(nowP);
    				switch (i) {
    				case 0:
    					nextP.x = nowP.x - 1;
    					break;
    				case 1:
    					nextP.x = nowP.x + 1;
    					break;
    				case 2:
    					nextP.y = nowP.y - 1;
    					break;
    				case 3:
    					nextP.y = nowP.y + 1;
    					break;
    				}
    
    				if (nextP.x < 0 || nextP.x >= M || nextP.y < 0 || nextP.y >= N)
    					continue;
    
    				if (visit[nextP.x][nextP.y] == 1)
    					continue;
    
    				nextP.step = nowP.step + 1;
    				// 入队。
    				myQueue.offer(nextP);
    				visit[nextP.x][nextP.y] = 1;
    			}
    		}
    
    		return -1;
    	}
    
    	public static void main(String[] args) throws IOException {
    		sc = new Scanner(System.in);
    		M = sc.nextInt();
    		N = sc.nextInt();
    		
    		//System.out.println(M + " " +  N);
    //		String temp;
    //		for(int i = 0; i < M ; i++)
    //		{
    //			temp = (sc.nextLine());
    //			for(int j = 0; j < N; j++)
    //				arr[i][j] = temp.charAt(j);
    //		}
    //		
    		for (int i = 0; i < M; i++) 
    		{
    			for (int j = 0; j < N; j++) 
    			{
    				arr[i][j] = (char) System.in.read();
    				if (arr[i][j] == '#')
    					visit[i][j] = 1;
    				else
    					visit[i][j] = 0;
    			}
    //			System.in.read();
    //			System.out.println(System.in.read()); // 消除 \n
    		}
    		
    		int x = -1, y = -1;
    		for (int i = 0; i < M; i++) {
    			for (int j = 0; j < N; j++) {
    				if (arr[i][j] == '@') {
    					x = i;
    					y = j;
    					break;
    				}
    			}
    			if (x != -1)
    				break;
    		}
    
    		int cost = bfs(x, y);
    		if (cost == -1)
    			System.out.println("Impossibility!");
    		else
    			System.out.println(cost);
    	}
    
    }

**另一个代码**

#include <stdio.h>
    #include <stdlib.h>
    
    #define NODEMAXNUM	100000 //90//
    #define INIF	100000
    typedef struct Node {
    	int x;
    	int y; //坐标
    	char c;
    	int step; //距离开始节点最短距离的值。
    	int visited; //0 未访问过， 1 访问过。   //使用过. 0 未入队。 1 在队中。 2 出队了，使用过
    }Node;
    
    Node nodeArr[105][105];
    char arr[105][105];
    int M,N;
    
    
    
    //循环队列
    typedef struct Queue{
    	int size;
    	Node * nodeArr; //数组形式存储队列。
    	int front;//指向刚放置到队列中的位置。队列内。
    	int rear; //指向未使用过的位置。队列内。初始化-1
    	//front rear指向队列外，或者队列内的，或者一个队列内一个队列外，不同的指向，对于出队入队是有区别的。
    }Queue;
    
    
    void initQueue(Queue * queue)
    {
    	queue->nodeArr = (Node*)malloc(NODEMAXNUM * sizeof(Node));
    	queue->size = 0;
    	queue->front = 0;
    	queue->rear = -1;
    }
    
    int isEmptyQueue(Queue * queue)
    {
    
    	if(queue->size == 0)
    		return 1;
    	else
    		return 0;
    }
    
    int isFullQueue(Queue * queue)
    {
    	if(queue->size ==  NODEMAXNUM)
    		return 1;
    	else
    		return 0;
    
    }
    
    int getQueueLen(Queue *queue)
    {
    	return queue->size;
    }
    
    //入队。从队尾入队。
    int EnQueue(Queue* queue, Node node)
    {
    	if(isFullQueue(queue))
    	{
    		printf("Queue is full\n");
    		return -1;
    	}
    	//因为有isFull 和isEmpty的判断，使得入队和出队不用担心front和rear的问题。
    	queue->rear++;
    	if(queue->rear == NODEMAXNUM)
    		queue->rear = 0;
    	queue->nodeArr[queue->rear] = node;
    	
    	queue->size = queue->size + 1;
        return 0;
    }
    //出队。从队首出队。 像排队一样。
    int DeQueue(Queue* queue, Node* node)
    {
    	if(isEmptyQueue(queue))
    	{
    		printf("Queue is empty\n");
    		return -1;
    	}
    
    	*node = queue->nodeArr[queue->front];
    	queue->front = (queue->front + 1) % NODEMAXNUM;
    	queue->size = queue->size - 1;
        return 0;
    }
    
    int DestroyQueue(Queue* queue)
    {
    	if(!queue)
    		return -1;
    	queue->size = 0;
    	if(queue->nodeArr)
    		free(queue->nodeArr); 
    	queue->front = 0;
    	queue->rear = 0;
    	return 0;
    }
    
    int isValidNode(Node nextNode)
    {
    	if(nextNode.x < 0 || nextNode.x > M -1 || nextNode.y < 0 || nextNode.y > N -1)
    		return 0;
    
    	if(nextNode.visited == 1)
    		return 0;
    
    	if(nextNode.c == '#')
    		return 0;
    	return 1;
    }
    
    
    int BFS(Node begin)
    {
    	Queue queue;
    	initQueue(&queue);
    
    	nodeArr[begin.x][begin.y].step = 0;
    	nodeArr[begin.x][begin.y].visited = 1;
    	EnQueue(&queue, nodeArr[begin.x][begin.y]);
    	
    
    	Node nextNode , firstNode;
    	while(isEmptyQueue(&queue) != 1)
    	{
    		DeQueue(&queue, &firstNode);
    
    		
    		//if(firstNode.x == end.x && firstNode.y == end.y)
    		if(firstNode.c == '*')
    		{
    			DestroyQueue(&queue);
    			return firstNode.step;
    		}
    
    		for(int i = 0; i < 4; i++)
    		{
    			switch(i)
    			{
    				case 0:
    				nextNode.x = firstNode.x - 1;
    				nextNode.y = firstNode.y;
    				break;
    				case 1:
    				nextNode.x = firstNode.x + 1;
    				nextNode.y = firstNode.y;
    				break;
    				case 2:
    				nextNode.x = firstNode.x;
    				nextNode.y = firstNode.y - 1;
    				break;
    				case 3:
    				nextNode.x = firstNode.x;
    				nextNode.y = firstNode.y + 1;
    				break;
    			}
    			if(!isValidNode(nodeArr[nextNode.x][nextNode.y]))
    				continue;
    			
    			//复杂.说明设计的不好。
    			nodeArr[nextNode.x][nextNode.y].visited = 1;
    			nodeArr[nextNode.x][nextNode.y].step = nodeArr[firstNode.x][firstNode.y].step + 1;
    			EnQueue(&queue, nodeArr[nextNode.x][nextNode.y]);
    			//nextNode.visited = 1;
    			//nextNode.step = firstNode.step + 1;
    			//EnQueue(&queue, nextNode);
    		}
    	}
    	return -1;
    }
    
    
    int main()
    {
        scanf("%d%d",&M,&N);
        
        // getchar();//消除 \n
        // for(int i = 0; i < M ;i++)
        // {
        //     for (int j = 0; j < N; j++)
        //     {
        //         scanf("%c",&nodeArr[i][j].c);
        //         nodeArr[i][j].x = i;
        //         nodeArr[i][j].y = j;
        //         nodeArr[i][j].step = INIF;
        //         nodeArr[i][j].visited = 0;
        //     }
        //     getchar(); //消除 \n
            
        // }
        
    	for(int i=0;i<M;i++)
            scanf("%s",arr[i]);
    
        int x1 = -1 ,y1 = -1;
        for(int i = 0; i < M; i++)
        {
            for(int j = 0; j < N; j++)
            {
            	nodeArr[i][j].c= arr[i][j];
            	nodeArr[i][j].x = i;
                nodeArr[i][j].y = j;
            	nodeArr[i][j].step = INIF;
                nodeArr[i][j].visited = 0;
    
                if(nodeArr[i][j].c == '@')
                {
                    x1 = i;
                    y1 = j;
                }
                // if(nodeArr[i][j].c == '*')
                // {
                // 	x2 = i;
                // 	y2 = j;
                // }
    
            }
        }
    
    
        int cost = BFS(nodeArr[x1][y1]);
    
        if( cost == -1)
        	printf("Impossibility!\n");
        else
        	printf("%d\n", cost);
        
        return 0;
    }

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

ertong

还是转战LeetCode吧。
心累。
在另一个兄弟的题解，无法通过的原因，可能也是因为输入的问题。
心累。

2019-06-17 16:07:53

ertong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

【偶数求和】（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

母牛的故事（C语言代码）

找寻小妖-题解(C语言代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

星期判断机（C语言代码）

核桃的数量（C语言代码）

C二级辅导-统计字符（C语言代码）

震宇大神的杀毒软件（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

多输入输出练习2 （C语言代码）

printf基础练习（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C二级辅导-等差数列（C语言代码）

ertong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

【偶数求和】 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

母牛的故事 （C语言代码）

找寻小妖-题解(C语言代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

星期判断机 （C语言代码）

核桃的数量 （C语言代码）

C二级辅导-统计字符 （C语言代码）

震宇大神的杀毒软件 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

多输入输出练习2 （C语言代码）

printf基础练习 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C二级辅导-等差数列 （C语言代码）

【偶数求和】（C语言代码）

母牛的故事（C语言代码）

　　评论区

星期判断机（C语言代码）

核桃的数量（C语言代码）

C二级辅导-统计字符（C语言代码）

震宇大神的杀毒软件（C语言代码）

printf基础练习（C语言代码）

C二级辅导-等差数列（C语言代码）